template

快速排序

int huafen(int A[], int L, int R)
{
    int mid = A[L];
    while(L<R)
    {
        while(L < R && A[R] >= mid) R--;
        A[L] = A[R];
        while(L < R &&A[L] <= mid) L++;
        A[R] = A[L];
    }
    A[L] = mid;
    return L;
}
void Qsort(int A[], int L, int R){
    if (L>=R) return;   
    int M = huafen(A,L,R);
    Qsort(A,L,M-1);
    Qsort(A,M+1,R);
}

二分

左半边界，第一个 ≥ 目标值的元素。
while(l<r)
{
    int mid = l+r >> 1;
    if(q[mid] >= x) r = mid;
    else l = mid+1;
}    
    
右半边界，最后一个 ≤ 目标值的元素。
while(l<r)
{
    int mid = l+r+1 >> 1;
    if(q[mid] <= x) l = mid;
    else r = mid - 1;
}

二分答案

while (left <= right) {
      int mid = left + (right - left) / 2;  // 计算中间值
      if (check(mid)) {  // 检查 mid 是否满足条件
          ans = mid;     // 更新答案
          right = mid - 1;  // 尝试更小的值
      } else {
          left = mid + 1;  // 尝试更大的值
      }
  }

逆置

void rev(int arr[],int n)
{
    int tmp;
    for(int i = 0; i < n/2; i++)
    {
        tmp = arr[i];
        arr[i] = arr[n-i-1];
        arr[n-i-1] = tmp;
    }
    return ;
}

2020

1.设计思想

2.代码

3.复杂度

4.改进

2020

基于“顺序表”的算法训练

真题

2010

1.设计思想

逆置前 p 个元素
逆置剩余 n-p 个元素
整体逆置整个数组

2.代码

void print(int arr[],int n)
{
  for(int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void reverse_(int arr[], int n)
{
    int tmp;
    for(int i = 0; i < n/2; i++)
    {
        tmp = arr[i];
        arr[i] = arr[n-i-1];
        arr[n-i-1] = tmp;
    }
}

void trans(int arr[], int p, int n)
{
    reverse_(arr,p);
    print(arr,n);
    reverse_(arr+p, n-p);
    print(arr,n);
    reverse_(arr,n);
    print(arr,n);
}

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9};
    trans(arr,3,9);
}

3.复杂度

时间复杂度O(n)，空间复杂度O(1)

2011

1.设计思想

计算两个序列合并后的中位数位置 n。因为合并后的序列长度为 2L，所以中位数位置为 (2L + 1) / 2 - 1（这里减1是因为数组下标从0开始）。
使用两个指针 i和 j分别指向序列 A和 B的起始位置。
遍历 n次，每次比较 A[i]和 B[j]的大小，将较小的元素的指针后移一位。
遍历结束后，比较 A[i]和 B[j]的大小，较小的那个元素就是两个序列的中位数。

2.代码

#include <iostream>
using namespace std;
int find_mid(int A[],int B[], int L)
{
    int n = (2*L+1)/2;
    n-=1;
    int i = 0, j = 0;
    for(int k=0;k<n;k++)
    {
        if(A[i]>B[j])
            j++;
        else
             i++;
    }
    if (A[i] > B[j])
         return B[j];
    else
         return A[i];
}
int main()
{
    int L = 5;
    int A[10] = {11,13,15,17,19};
    int B[10] = {2,4,6,8,20};
    cout <<find_mid(A,B,L) <<endl;
}

3.复杂度

时间复杂度：算法中使用了一个 for循环来遍历 n次，其中 n = (2L + 1) / 2 - 1，因此时间复杂度为 O(L)。
空间复杂度：算法只使用了常数级别的额外空间（指针 i、j和一些临时变量），因此空间复杂度为 O(1)。

4. 改进

若此序列不是相等长度，还需考虑A和B长度不等时的越界问题。

2013

1. 设计思想

首先构造一个辅助数组arr[N]（由于ai<n），下标对应元素的值，下标个数对应元素的个数，刚开始时初始化为0。
从序列首部开始遍历序列，每遍历一个元素就进行arr[元素]++操作。
遍历到序列首部，得出各个元素的出现频次，循环arr数组判断是否有出现次数大于n/2的元素，若有则输出元素，无则返回1。

2.代码

int find_master(int a[],int n)
{
    int *arr = (int *) malloc(n * sizeof(int));
    memset(arr, 0, n* sizeof(int)); //所有元素频次为0
    for(int i = 0; i < n; i++)
    {
        arr[a[i]]++;    //对应元素出现频次+1
    }
    int max_cnt = n/2;
    for(int i = 0; i < n; i++)
    {
        if(arr[i] > max_cnt)    //找到出现频次大于n/2的元素
        {
            free(arr);
            return i;
        }
    }
    free(arr);
    return -1;  //没有找到
}
int main()
{
    int A[] = {0,5,5,3,5,7,5,5};
    int B[] = {0,5,5,3,5,1,5,7};
    cout << find_master(A,8) << " " << find_master(B,8) << endl;
}

3. 复杂度

使用了一个辅助数组arr[n]，因此空间复杂度为O(n)，使用两次for循环遍历n次，因此时间复杂度为O(n)。

4. 改进

由于此序列元素大小都小于n，因此可以采用辅助数组。

2016

1.设计思想

当n为偶数时，集合A1的大小等于A2的大小，当n为奇数时，集合A1和集合A2大小相差1
对数组从小到大排序
当n为偶数时，前n/2个元素属于A1，后n/2个元素属于A2
当n为奇数时，前n/2个元素属于A1.后n/2+1个元素属于A2
上面n/2为向下整除

2.代码

int huafen(int A[], int L, int R)
{
    int mid = A[L];
    while(L<R)
    {
        while(L < R && A[R] >= mid) R--;
        A[L] = A[R];
        while(L < R &&A[L] <= mid) L++;
        A[R] = A[L];
    }
    A[L] = mid;
    return L;
}
void Qsort(int A[], int L, int R){
    if (L>=R) return;   
    int M = huafen(A,L,R);
    Qsort(A,L,M-1);
    Qsort(A,M+1,R);
}

int one_to_two(int n,int A[])
{
    int *A1 = (int *)malloc(n * sizeof(int));
    int *A2 = (int *)malloc(n * sizeof(int));
    Qsort(A, 0, n-1);
    int sum1 = 0, sum2 = 0;
    int half = n / 2; 
    for (int i = 0; i < half; i++) {
        sum1 += A[i];
    }
    for (int i = half; i < n; i++) {
        sum2 += A[i];
    }   
    return sum2 - sum1; 
}


int main()
{
    int A[] = {3,2,1,4,5};
    printf("%d\n",one_to_two(5,A));
    int B[] = {1,6,4,5};
    printf("%d\n",one_to_two(4,B));
}

3.复杂度

时间复杂度O(nlogn)，空间复杂度O(nlogn)

4.改进

2018

1. 设计思想

对数组进行排序，使得数组从小到大有序。
从前向后遍历数组
1. 负数直接跳过
2. 特殊判断第一个正数，若不为1，则直接输出最小正数为1
3. 遍历其余正数，比较两个相邻元素A[i-1],A[i]。
  1. 若A[i-1]=A[i]或A[i-1]+1=A[i]，继续循环
  2. 若不符合条件，即可以插入正整数，将A[i-1]+1输出。
4. 若遍历完成，则最小正整数只能最最大元素+1

2.代码

int huafen(int A[], int l, int r)
{
    int mid = A[l];
    while(l < r)
    {
        while(l<r && A[r] >= mid) r--;
        A[l] = A[r];
        while(l<r && A[l] <= mid) l++;
        A[r] = A[l];
    }
    A[l] = mid;
    return l;
}

void qucik_sort(int A[], int l, int r)
{ 
    if (l >= r) return;
    int mid = huafen(A, l, r);
    qucik_sort(A, l, mid-1);
    qucik_sort(A, mid+1, r);

}

int find_min(int A[], int n)
{
    qucik_sort(A, 0, n-1);
    int i = 0;
    for(int i = 0; i < n; i++)  // 找第一个正数
    {
        if(A[i] > 0)
            break;
    }
    if(A[i] != 1)   // 特判1是不是最小正数
        return 1;
    i+=1;
    for(;i<n;i++)
    {
        if(A[i-1] == A[i] || A[i-1]+1 == A[i])  // 判断是否连续
            continue;
        else
            return A[i-1]+1;    // 返回第一个最小正数
    }
    return A[n-1]+1;    
}

int main()
{
    int A[] = {-5,3,2,3};
    int B[] = {1,2,3};
    cout << find_min(A, 4) << endl;
    cout << find_min(B, 3) << endl;
}

3.复杂度

时间复杂度O(nlogn)，空间复杂度O(nlogn)

4.改进

由于只有n个元素，最多填满1~n的正整数，即可能的最小正整数只能在1-n+1内取到，对于在1-n+1范围外的元素，直接丢弃即可。因此新建一个辅助布尔数组B[N]并初始化为0，使1-n+1的元素映射到下标0-n。循环数组A并标记对应B数组下标为true。最后从下标0开始遍历B数组，若对应a[i]值为false，则最小正数为i+1。

2020

1.设计思想

创建变量len描述最小距离。
使用三层循环遍历数组，得到三元组后计算距离，若小于min，则更新min为该距离值。
当循环遍历完后，该距离值即为最小距离值。

2.代码

int find_minnum(int S1[], int lenS1, int S2[], int lenS2, int S3[], int lenS3)
{
    int len = abs(S1[0] - S2[0]) + abs(S2[0]-S3[0]) + abs(S3[0]- S1[0]);
    for(int i = 0; i < lenS1; i++)
        for(int j = 0; j < lenS2; j++)
            for(int k = 0; k < lenS3; k++)
            {
                int temp = abs(S1[i] - S2[j]) + abs(S2[j]-S3[k]) + abs(S3[k]- S1[i]);
                len = min(len, temp);
            }
    return len;

}
int main() {
    int S1[] = {-1,0,9};
    int S2[] = {-25,-10,10,11};
    int S3[] = {2,9,17,30,41};
    cout << find_minnum(S1,3,S2,5,S3,5) << endl;
}

3.复杂度

时间复杂度O(n^3)，空间复杂度O(1)

4.改进

使用三指针算法

初始化三个指针 i, j, k分别指向 S1, S2, S3的开头。
计算当前三个元素的绝对差之和，并更新最小值。
移动最小的那个元素的指针（因为数组有序，这样可以逐步逼近最小值）。
时间复杂度降至 O(lenS1 + lenS2 + lenS3)，适用于大规模数据。

“顺序表”基本功训练

1

若顺序表为空，则直接返回。
否则维护一个pos变量表示最小元素的位置，遍历顺序表，比较当前元素与pos位置元素的大小，若小于则更新pos。
将最小元素输出，并将最后一个元素赋值到最小元素位置，修改顺序表长度。

2.

双指针法：

维护一个变量k，表示顺序表中与x不相等的元素个数，遍历数组，循环变量为i
若arr[i]不为x，则arr[k]=arr[i]，k++
若arr[i]为x，则continue

方法二：

变量k记录与x相等的元素个数
若arr[i]为x，k++
若arr[i] 不为x，则arr[i-k]=arr[i]

方法三：

通过头指针 i和尾指针 j从序列两端向中间遍历，动态交换元素以实现高效删除。类似归并排序，将要删除的元素放到队尾。

3.

首先判断s<t和顺序表非空
用变量k维护不会被删除的元素个数
若arr[i]在范围外，则arr[k] = arr[i]; k++
若arr[i]在范围内，continue

4.

方法一：

由于顺序表是有序的，因此可以分割为多个值重复的子顺序表

变量k记录不重复的元素个数，变量tmp记录当前访问的可能重复元素。
初始tmp=arr[0]，k=1;
从下标1开始遍历顺序表，i表示遍历的顺序
1. 若arr[i]!=tmp，则说明上个重复元素遍历完毕，更新tmp为arr[i]，arr[k++]=arr[i]
2. 若arr[i]==tmp，说明元素重复，continue

方法二：

维持一个指针j=0，指向前面的有序非重复顺序表的最后一个元素
变量i从1开始遍历顺序表
1. 若大于j指向的元素，则赋值给j++,
2. 否则continue

拓展：

若为无序线性表，则采用散列表的思想，时间复杂度O(n)
若题目改为保留至多两次重复（如 [1,1,1,2] → [1,1,2]），如何修改算法？

解法：增加计数器，当 arr[i] == arr[j]且出现次数 <2时保留。

5.

按序遍历线性表
若元素小于x，循环继续
若元素等于x，则tmp=arr[i]，arr[i]=arr[i+1],arr[i+1]=tmp return
若元素大于x，则将大于x的元素tmp以及之后的元素后移(从后向前遍历,arr[i+1]=arr[i])，然后插入x到tmp的位置

优化：

使用二分查找

顺序表的“逆置”在算法题中的应用

1.

void rev(int arr[],int n)
{
    int tmp;
    for(int i = 0; i < n/2; i++)
    {
        tmp = arr[i];
        arr[i] = arr[n-i-1];
        arr[n-i-1] = tmp;
    }
    return ;
}
int main() {
    int arr[] = {1,2,3,4,5,6};
    rev(arr,6);
    for(int i = 0; i < 6; i++)
    {
        cout << arr[i] << " ";
    }
}

2.

先进行整体逆置，在分别对a，b两个线性表进行逆置。

void print(int arr[])
{
  for(int i = 0; i < 9; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void rev(int arr[],int n)
{
    int tmp;
    for(int i = 0; i < n/2; i++)
    {
        tmp = arr[i];
        arr[i] = arr[n-i-1];
        arr[n-i-1] = tmp;
    }
    return ;
}

void revv(int arr[], int n, int m)
{
    rev(arr,n+m);
    print(arr);
    rev(arr+n,m);
    print(arr);
    rev(arr,n);
    print(arr);
}

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9};
    revv(arr,3,6);
}
// 9 8 7 6 5 4 3 2 1                                             <
// 9 8 7 1 2 3 4 5 6                                             <
// 7 8 9 1 2 3 4 5 6                                             <

基于“链表”的算法训练

单链表的基本功训练

1.

typedef struct LNode{
    int data;
    struct LNode* link;
}Lnode,*Linklist;

void print(Linklist L)
{
    Linklist p = L->link;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}

void add(Linklist L,int x)		//头插法建立单链表
{
    Linklist node =  (Linklist)malloc(sizeof(LNode));
    node->link = L->link;
    L->link = node;
    node->data = x;
}
    
void del(Linklist L, int x) {
    Linklist p = L;
    while(p->link != NULL) {
        if(p->link->data == x) {
            Linklist tmp = p->link;
            p->link = tmp->link;
            free(tmp);
        } else {
            p = p->link;
        }
    }
}

int main()
{
    Linklist head = (Linklist)malloc(sizeof(LNode));
    head->link = NULL;
    add(head, 3);
    add(head, 1);
    add(head, 2);
    add(head, 3);
    add(head, 4);
    add(head, 3);
    print(head);
    del(head,3);
    print(head);
}

2.

typedef struct LNode{
    int data;
    struct LNode* link;
}LNode, *Linklist;

void print(Linklist L)
{
    Linklist p = L->link;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}

//尾插法建立链表
void add(Linklist L,int x, Linklist& p)         //注意传入的是引用地址
{
    Linklist node =  (Linklist)malloc(sizeof(LNode));
    p->link = node;
    node->data = x;
    node->link = NULL;
    p = node;
}

void delmin(Linklist L) {
    Linklist minNodepre = L;	// minNodepre 指向最小值节点的前驱
    Linklist p = L;
    while(p->link != NULL) {		
        if(p->link->data < minNodepre->link->data)
        {
            minNodepre = p;
        }
        p = p->link;
    }
    Linklist tmp = minNodepre->link;
    minNodepre->link = tmp->link;
    free(tmp);
}

int main()
{
    Linklist head = (Linklist)malloc(sizeof(LNode));
    Linklist p = head;
    head->link = NULL;
    add(head, 3,p);
    add(head, 1,p);
    add(head, 2,p);
    add(head, 3,p);
    add(head, 4,p);
    add(head, 3,p);
    print(head);
    delmin(head);
    print(head);
}

3.

typedef struct LNode{
    int data;
    struct LNode* link;
}Lnode,*Linklist;

void print(Linklist L)
{
    Linklist p = L->link;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}

void add(Linklist L,int x)		//头插法建立单链表
{
    Linklist node =  (Linklist)malloc(sizeof(LNode));
    node->link = L->link;
    L->link = node;
    node->data = x;
}
    
void delbet(Linklist L, int l, int r) {
    Linklist p = L;
    while(p->link != NULL) {
        if(p->link->data >= l && p->link->data <= r) {
            Linklist tmp = p->link;
            p->link = tmp->link;
            free(tmp);
        } else {
            p = p->link;
        }
    }
}

int main()
{
    Linklist head = (Linklist)malloc(sizeof(LNode));
    head->link = NULL;
    add(head, 3);
    add(head, 1);
    add(head, 2);
    add(head, 5);
    add(head, 4);
    add(head, 3);
    print(head);
    delbet(head,2,3);
    print(head);
}

4.

typedef struct LNode{
    int data;
    struct LNode* link;
}Lnode,*Linklist;

void print(Linklist L)
{
    Linklist p = L->link;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}

void add(Linklist L,int x)		//头插法建立单链表
{
    Linklist node =  (Linklist)malloc(sizeof(LNode));
    node->link = L->link;
    L->link = node;
    node->data = x;
}
    
void delcommon(Linklist L) {
    Linklist p = L->link;
    if(p == NULL)
        return ;
    while(p->link != NULL) {
        if(p->link->data == p->data)
        {
            Linklist tmp = p->link;
            p->link = tmp->link;
            free(tmp);
        }
        else 
            p = p->link;
    }
}

int main()
{
    Linklist head = (Linklist)malloc(sizeof(LNode));
    head->link = NULL;
    add(head, 70);
    add(head, 51);
    add(head, 42);
    add(head, 42);
    add(head, 42);
    add(head, 30);
    add(head, 21);
    add(head, 10);
    add(head, 10);
    add(head, 7); 
    print(head);
    delcommon(head);
    print(head);
}

5.

typedef struct LNode{
    int data;
    struct LNode* link;
}Lnode,*Linklist;

void print(Linklist L)
{
    Linklist p = L->link;
    while(p!=NULL && p != L)      //防止无限循环
    {
        printf("%4d ",p->data);
        p = p->link;
    }
    printf("\n");

}

void add(Linklist L,int x)		//头插法建立单链表
{
    Linklist node =  (Linklist)malloc(sizeof(LNode));
    node->link = L->link;
    L->link = node;
    node->data = x;
}

void merge(Linklist L1, Linklist L2)
{
    if(L2->link==L2)        //需要特判，否则L1的循环链不对
    {
        free(L2);
        return;
    }

    Linklist p = L1;
    while(p->link != L1)
    {
        p=p->link;
    }
    p->link = L2->link;
    while(p->link!=L2)
    {
        p=p->link;
    }
    p->link = L1;
    free(L2);
} 

int main()
{
    Linklist h1 = (Linklist)malloc(sizeof(LNode));
    h1->link = h1;     //只需更改这个就能变成循环单链表,还需更改print函数
    add(h1, 70);
    add(h1, 51);
    add(h1, 42);

    Linklist h2 = (Linklist)malloc(sizeof(LNode));
    h2->link = h2;
    add(h2, 42);
    add(h2, 42);
    add(h2, 30);
 
    print(h1);
    print(h2);

    merge(h1,h2);
    print(h1);
}

真题

2009

1.设计思想

用指针p和q遍历链表
当指针p遍历到第k-1个位置，指针q出发。
指针p遍历到链表尾部时，指针p指向倒数第1个结点，指针q指向倒数第k个节点。
若指针q没有出发，说明链表长度小于k，返回0。否则能找到该值，输出该节点data域的值，返回1。

2.代码

typedef struct LNode{
    int data;
    struct LNode* link;
}LNode, *LinkList;


void add(LinkList L, int x)
{
    LinkList node = (LinkList)malloc(sizeof(LNode));
    node->link = L->link;
    node->data = x;
    L->link = node;
}

int GetData(LinkList L, int npos)
{
    LinkList p = L;
    LinkList q = L;
    while(p->link != NULL && --npos>0)
        p=p->link;
    while(p->link != NULL)
    {
        p=p->link;
        q=q->link;
    }
    if(q==L)
        return 0;
    else
     {
        printf("%d\n", q->data);
        return 1;
     }
}

int main() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->link = NULL;
    add(L,1);
    add(L,2);
    add(L,3);
    add(L,4);
    add(L,5);
    GetData(L,1);
    GetData(L,2);
    GetData(L,3);
    GetData(L,4);
    GetData(L,5);
    GetData(L,6);
}

3.复杂度

由于只需要遍历一次链表，时间复杂度为O(n)，只需要两个额外指针，空间复杂度为O(1)。

4.改进

2012

1.设计思想

采用快慢指针，首先对str1和str2链表进行遍历求出两个链表的长度len1和len2。
创建两个指针变量p，q分别指向str1和str2，当A的长度大于B时，指针p先出发，当p遍历到第tmp个节点时，q出发，此时p和q到链尾的距离链尾的距离相同。同理，若A的长度小于B时，q先出发。
然后p和q继续遍历，若p和q的地址相同，则是共同后缀的起始位置。

注意读懂题意，题目中的ing已经是共同后缀，指针相同则是位置p


1. 创建指针变量pos，指向str1可能出现的共同后缀起始位置。p和q都出发后。记录当前节点的位置为pos。匹配后面的结点：
   1. 若遍历到队尾节点元素对应相等，则pos就是共同后缀的起始位置
   2. 若中间有不同节点，则更新当前pos变量
2. 若pos不是队尾，则pos就是共同后缀的起始位置。若pos是队尾且链表队尾元素相同，则最后一个节点元素是共同元素，否则无共同元素；

2.代码

typedef struct LNode
{
    char data;
    struct LNode* next;
}LNode, *LinkList;

void print(LinkList L)
{
    LinkList p = L->next;
    while(p!=NULL)
    {
        printf("%16c",p->data);
        p = p->next;
    }
    printf("\n");
    p = L->next;
    while(p!=NULL)
    {
        printf("%16p",p);
        p = p->next;
    }
    printf("\n");
}

int lenstr(char * str)
{
    int len = 0;
    while(str[len]!='\0')   len++;
    return len;
}

void ins(LinkList L1,LinkList L2,char* str1, char* str2, char* str3)
{
    for(int i = lenstr(str3)-1;i>=0; i--)   //插入共同后缀,只需要创建一个节点
    {
        LinkList tmp = (LinkList)(malloc(sizeof(LNode)));
        tmp->next = L1->next;
        tmp->data = str3[i];
        L1->next = tmp;
        tmp->next = L2->next;
        tmp->data = str3[i];
        L2->next = tmp;
    }

    for(int i = lenstr(str1)-1;i>=0; i--)
    {
        LinkList tmp = (LinkList)(malloc(sizeof(LNode)));
        tmp->next = L1->next;
        tmp->data = str1[i];
        L1->next = tmp;
    }
     for(int i = lenstr(str2)-1;i>=0; i--)
    {
        LinkList tmp = (LinkList)(malloc(sizeof(LNode)));
        tmp->next = L2->next;
        tmp->data = str2[i];
        L2->next = tmp;
    }
}

int GetLen(LinkList L)
{
    int len = 0;
    LinkList p = L;
    while(L->next != NULL)
    {
        L=L->next;
        len++;
    }
    return len;
}

LinkList findPos(LinkList L1, LinkList L2)
{
    int len1 = GetLen(L1);
    int len2 = GetLen(L2);
    LinkList p = L1;
    LinkList q = L2;
    if(len1 > len2) 
    {
        while(len1--!=len2)
        {
            p= p->next;
        }
    }
    else {
        while(len2--!=len1)
        {
            q = q->next;
        }
    }
    //相等则len1，len2同时出发
    while(q->next!=NULL && p->next!=NULL)
    {
        p = p->next;
        q = q->next;
        if(q==p)    //返回共同后缀的起始地址
            return q;
    }
    return NULL;    //无共同后缀

}


int main()
{
    LinkList L1 = (LinkList)malloc(sizeof(LNode));
    LinkList L2 = (LinkList)malloc(sizeof(LNode));
    char str1[] = "load";
    char str2[] = "be";
    char str3[] = "ing";
    ins(L1,L2,str1,str2,str3);
    print(L1);
    print(L2);
    printf("%p",findPos(L1, L2));
}

3.复杂度

两次求链表长度，和两次遍历链表，str1长度为m，str2长度为n。时间复杂度为O(m+n)，无需额外辅助空间，空间复杂度O(1)。

4.改进

2015

1.设计思想

定义一个辅助布尔数组arr[n]记录该绝对值是否出现过
从链表开始遍历节点，若节点data的绝对值已经出现过，则删除该节点
否则记录该绝对值已经出现过

2.代码

typedef struct Node{
    int data;
    struct Node* link;
}Node,*LinkList;

void print(LinkList L)
{
    LinkList p = L;
    while(p->link!=NULL)
    {
        p=p->link;
        printf("%d ", p->data);
    }
    printf("\n");
}

void add(LinkList L,int x)
{
    LinkList tmp = (LinkList)malloc(sizeof(Node));
    tmp->link = L->link;
    tmp->data = x;
    L->link = tmp;
}

int abs_(int x)
{
    if(x>0) return x;
    else return -x;
}

void modify(LinkList L, int n)
{
    int* arr = (int*)malloc(sizeof(bool)*(n+1));
    for(int i = 0; i<=n;i++)
    {
        arr[i] = false;
    }
    LinkList p = L;
    while(p->link!=NULL)
    {
        if(arr[abs_(p->link->data)] == true)
        {
            LinkList tmp = p->link;
            p->link = tmp->link;
            free(tmp);
        }
        else {
            arr[abs_(p->link->data)] = true;
            p = p->link;
        }
    }
}

int main()
{
    LinkList L1 = (LinkList)malloc(sizeof(Node));
    L1->link = NULL;
    add(L1,15);
    add(L1,-7);
    add(L1,-15);
    add(L1,-15);
    add(L1,21);
    print(L1);
    modify(L1, 21);
    print(L1);
}

3.复杂度

需要遍历一次链表，时间复杂度O(m)，需要辅助数组arr[n]，空间复杂度O(n)

4.改进

2019

1.设计思想

求链表长度，分别取出链表的前半部分，后半部分，前半部分=后半部分，或前半部分+1=后半部分。
将链表前半部分进行逆置。
将后半部分插入前半部分

2.代码

typedef struct node
{
    int data;
    struct node* next;
} NODE;

void print(NODE* L)
{
    NODE* p = L;
    while(p->next!=NULL)
    {
        p=p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

void add(NODE* L, int x)
{
    NODE* node = (NODE*)malloc(sizeof(NODE));
    node->data = x;
    node->next = L->next;
    L->next = node;
}

void rev(NODE* L)
{
    NODE* pre = NULL;
    NODE* now = L->next;
    NODE* next = NULL;
    while(now!=NULL)
    {
        next = now->next;
        now->next = pre;
        pre = now;
        now = next;
    }
    L->next = pre;
}

int getLen(NODE* L)
{
    NODE* p = L->next;
    int cnt = 0;
    while(p!=NULL)
    {
        p = p->next;
        cnt++;
    }
    return cnt;
}

void transfer(NODE* L)
{
    NODE* p = L;     
    //NODE* L1 = NULL;    //指向后半部分指针
    int len = getLen(L);
    int pos = (len+1)/2;  //获取链表中间位置
    while(pos--!=0)     //中间位置的前一个节点
    {
        p=p->next;
    }
    NODE* L1 = (NODE*)malloc(sizeof(NODE));
    L1->next = p->next;
    p->next = NULL; //中间断开链表，分为两个链表
    rev(L1);     //逆置前半部分
    print(L1);
    print(L);
   
    NODE* pp = L->next;     //前半部分指针
    NODE* qq = L1->next;    //后半部分指针

    while (pp && qq) {
        NODE* tmp1 = pp->next;
        NODE* tmp2 = qq->next;
        pp->next = qq;
        qq->next = tmp1;
        pp = tmp1;
        qq = tmp2;
    }
    
 
}


int main()
{
    NODE* L = (NODE*)malloc(sizeof(NODE));
    add(L,1);
    add(L,2);
    add(L,3);
    add(L,4);
    //add(L,5);
    print(L);
    rev(L);
    print(L);
    printf("%d\n",getLen(L));
    transfer(L);
    print(L);
}

3.复杂度

时间复杂度O(n)，空间复杂度O(1)

4.改进

单链表的“原地逆置”技巧

1.

三指针法

使用 三个指针 pre、now、next遍历链表，逐个反转指针方向。

头插法

将原链表节点逐个取出，用 头插法 插入新链表，实现逆置。

typedef struct node
{
    int data;
    struct node* next;
} NODE;

void print(NODE* L)
{
    NODE* p = L;
    while(p->next!=NULL)
    {
        p=p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

void add(NODE* L, int x)
{
    NODE* node = (NODE*)malloc(sizeof(NODE));
    node->data = x;
    node->next = L->next;
    L->next = node;
}

void rev1(NODE* L)  //采用三个指针，遍历链表修改指针朝向
{
    NODE* now = L->next;
    NODE* pre = NULL; 
    NODE* next = NULL;
    while(now!=NULL)
    {
        next = now->next;
        now->next = pre;
        pre = now;
        now = next;
    }
    L->next = pre;
}

void rev2(NODE* L)  //使用头插法逆置
{
    NODE* p = L->next;
    L->next = NULL;
    while(p!=NULL)
    {
        NODE* q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

int main()
{
    NODE* L = (NODE*)malloc(sizeof(NODE));
    add(L,1);
    add(L,2);
    add(L,3);
    print(L);
    rev1(L);
    print(L);
    rev2(L);
    print(L);
}