基于“链表”的算法训练

单链表的基本功训练

1.

image-20250815205556617

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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.

image-20250815213658161

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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);
}

image-20250815215822020

3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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.

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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.

image-20250815225206297

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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

image-20250816213044739

1.设计思想

  1. 用指针p和q遍历链表

  2. 当指针p遍历到第k-1个位置，指针q出发。

  3. 指针p遍历到链表尾部时，指针p指向倒数第1个结点，指针q指向倒数第k个节点。

  4. 若指针q没有出发，说明链表长度小于k，返回0。否则能找到该值，输出该节点data域的值，返回1。

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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

image-20250817113844513

1.设计思想

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


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

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
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

image-20250817225413381

1.设计思想

  1. 定义一个辅助布尔数组arr[n]记录该绝对值是否出现过

  2. 从链表开始遍历节点，若节点data的绝对值已经出现过，则删除该节点

  3. 否则记录该绝对值已经出现过

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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

image-20250818122405570

1.设计思想

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

2.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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.

image-20250818111921397

  1. 三指针法

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

  1. 头插法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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);
}