数据结构-链表的经典面试题_数据结构单链表面试

作者：小丑西瓜9 | 2024-04-24 08:00:53

踩

数据结构单链表面试

在前面的博客中我们对链表做了一些基本操作，所以在此不再赘述。直接来看，有哪些和链表有关的面试题以及如何去实现它们。
1.头文件声明

linklist.h
#pragma once 

typedef char LinkNodeType;

typedef struct LinkNode
{
    LinkNodeType data;
    struct LinkNode *next;
}LinkNode;

//逆序打印链表
void LinkListReversePrint(LinkNode* head);

//链表逆序（先删除节点再头插）
void LinkListReverse(LinkNode** head);

//链表逆序（用三个指针）       
void LinkListReverse2(LinkNode** head);

//约瑟夫环
LinkNode* JosephCircle(LinkNode* head,int M);

//冒泡排序
void LinkListBubbleSort(LinkNode* head);

//将两个有序链表合并成一个有序链表
LinkNode* LinkListMerge(LinkNode* head1,LinkNode* head2);

//找一个链表的中间结点
LinkNode* LinkListFindMidNode(LinkNode* head);

//查找链表的倒数第k个结点
LinkNode* LinkListFindLastKNode(LinkNode* head,int k)

//删除链表的第倒数k个结点
void LinkListEraseLastKNode(LinkNode** head,int k);

//判断链表是否有环
LinkNode* LinkListHasCycle(LinkNode* head);

//判断环的长度
int  LinkListCycleLen(LinkNode* head);

//判断环的入口点
LinkNode* LinkListCycleEntry(LinkNode* head);

//判断两个链表是否相交
int LinkListCross(LinkNode* head1,LinkNode* head2);

//链表相交，求交点
LinkNode* LinkListHasCross(LinkNode* head1,LinkNode* head2);

//判断两个链表是否相交（链表可能带环）
int LinkListCrossWithCycle(LinkNode* head1,LinkNode* head2);

//链表相交，求交点
LinkNode* LinkListHasCrossWithCycle(LinkNode* heda1,LinkNode* head2);

//求两个已排序单链表中相同的数据
LinkNode* LinkListUnionSet(LinkNode* head1,LinkNode* head2);
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

2.各个函数的具体实现

//逆序打印单链表，采用递归的思想
void LinkListReversePrint(LinkNode* phead)
{
    if(phead != NULL)
    {
        if(phead->next != NULL)
        {
            LinkListReversePrint(phead->next); //递归打印
        }
        printf("%c ",phead->data);
    }
    return;
}

//逆序单链表，第一种方法，先删除结点再进行头插
void LinkListReverse(LinkNode** phead)
{
    if(phead == NULL)
        return;                //非法输入

    if(*phead == NULL)
        return;                //空链表

    if((*phead)->next == NULL)
        return;                //只有一个元素的链表

    LinkNode* cur = *phead;
    while(cur->next != NULL)
    {
        LinkNode* to_delete = cur->next;
        //删除这个结点
        cur->next = to_delete->next;
        //把刚删除的元素插入到链表头部
        to_delete->next = *phead;
        *phead = to_delete;
    }
}

//逆序单链表，第二种方法，通过不断修改三个指针的指向
void LinkListReverse2(LinkNode** phead)
{

    if(phead == NULL)
        return;                //非法输入

    if(*phead == NULL)
        return;                //空链表

    if((*phead)->next == NULL)
        return;                //只有一个元素的链表

    LinkNode* cur = (*phead)->next;
    LinkNode* pre = (*phead);
    pre->next = NULL;
    while(cur != NULL)
    {
        LinkNode* next = cur->next;
        //修改cur->next的指向
        cur->next = pre;
        //更新pre cur
        pre = cur;
        cur = next;

    }
    *phead = pre;

}

//约瑟夫环的实现
LinkNode* JosephCircle(LinkNode* head,int M)
{
    if(head == NULL)
        return NULL;           //空链表

    LinkNode* cur = head;
    while(cur->next != cur)
    {
        int i = 1;
        //定义的基数M,一次查找走M步
        for( ;i < M;i++)
        {
            cur = cur->next;
        }
        //cur指向的元素，就是倒霉的人，即要删除的结点
        printf("%c\n",cur->data);
        //删除这个结点
        cur->data = cur->next->data;
        LinkNode* to_delete = cur->next;
        cur->next = to_delete->next;
        DestroyNode(to_delete);
    }
    return cur;
}

//交换函数
void Swap(LinkNodeType* a,LinkNodeType* b)
{
    LinkNodeType tmp = *a;
    *a = *b;
    *b = tmp;
    return;
}
//冒泡排序
void LinkListBubbleSort(LinkNode* phead)
{
    if(phead == NULL)
        return;    //空链表

    LinkNode* count = phead;//记录冒多少次
    LinkNode* tail = NULL;
    for( ;count != NULL;count = count->next)
    {
        LinkNode* cur = phead;//每冒一次需要遍历链表的长度
        for( ;cur->next != tail;cur = cur->next)
        {
            if(cur->data > cur->next->data)//升序
            {
                Swap(&cur->data,&cur->next->data);
            }
        }
        tail = cur;//更新tail指针
    }
    return;
}
//合并两个有序链表，合并后依然有序
 LinkNode* LinkListMerge(LinkNode* head1,LinkNode* head2)
{
    //如果两个链表任意一个为空，则返回另外一个链表
    if(head1 == NULL)
        return head2;
    if(head2 == NULL)
        return head1;

    LinkNode* cur1 = head1;
    LinkNode* cur2 = head2;
    //定义新链表的头结点和尾结点
    LinkNode* new_head = NULL;
    LinkNode* new_tail = NULL;
    //遍历两个链表
    while(cur1 != NULL && cur2 != NULL)
    {
        //如果cur1的值小于cur2,就把cur1插入新链表，然后将 cur1指向它的下一个结点 ；否则，将cur2插入新链表，更新cur2指针
    if(cur1->data < cur2->data)
        {
            if(new_tail == NULL)
            {
                new_head = new_tail = cur1;
            }
            else
            {
                new_tail->next = cur1;
                new_tail = new_tail->next;
            }
            cur1 = cur1->next;
        }
        else
        {

            if(new_tail == NULL)
            {
                new_head = new_tail = cur2;
            }
            else
            {
                new_tail->next = cur2;
                new_tail = new_tail->next;
            }
            cur2 = cur2->next;
        }
    }
    //有一方已经先到达末尾，需要把剩余的一方追加到新链表后面
    if(cur1 != NULL)
    {
        new_tail->next = cur1;
    }
    else
    {
        new_tail->next = cur2;
    }
    return new_head;
}

//查找链表的中间结点，定义快慢指针只遍历一次链表
LinkNode* LinkListFindMidNode(LinkNode* phead)
{
    if(phead == NULL)
    {
        return NULL;//空链表
    }
    LinkNode* slow = phead;
    LinkNode* fast = phead;
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;//慢指针一次走一步
        fast = fast->next->next;//快指针一次走两步
    }
    return slow;
}

//查找倒数第k个结点
LinkNode* LinkListFindLastKNode(LinkNode* phead,int k)
{
    if(phead == NULL)
        return;           //空链表

    LinkNode* fast = phead;
    LinkNode* slow = phead;
    // 让快指针先走k步
    int i = 0;
    for( ;i < k;i++)
    {
        if(fast == NULL)
        {
            break;
        }
        fast = fast->next;
    }
    if(i != k)
    {
        //没走完,k的长度超过了链表长度
        return NULL;
    }
    while(fast != NULL)
    {
        //快慢指针每次各走一步，快指针指向空的时候，慢指针刚好指向倒数第K个结点
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

//删除倒数第K个结点，思想找到它的一个结点
void LinkListEraseLastKNode(LinkNode** phead,int k)
{
    if(phead == NULL)
        return;             //非法输入
    if(*phead == NULL)
        return;             //空链表

    int len = LinkListSize(*phead);
    if(k == len)
    {
        //要删除的元素，刚好是第一个元素，头删
        LinkNode* to_delete = *phead;
        *phead = (*phead)->next;
        DestroyNode(to_delete);
        return;
    }
    //遍历链表，找到要删除结点的前一个结点
    LinkNode* pre = *phead;
    int i = 0;
    for(;i < len-k-1;i++)
    {
        pre = pre->next;
    }
    //循环结束后，表明pre节点已经指向了要删除元素的前一个结点
    LinkNode* to_delete = pre->next;
    pre->next = to_delete->next;
    DestroyNode(to_delete);
    return;
}

//判断链表是否带环
//   第一种思路：建一个顺序表，初始化后，在遍历链表同时
//在顺序表里查找该元素，如果该元素已经存在，说明链表带环，
//如果不存在，就将该元素插入到顺序表中。但是这种算法时间
//复杂度为O(n^2),空间复杂度为O(n).
//   第二种思路，定义快慢指针，让快指针一次走两步，慢指针
//走一步，如果快慢指针最后相遇，说明该链表带环。这种算法
//时间复杂度为O(n),空间复杂度为O(1).

LinkNode* LinkListHasCycle(LinkNode* phead)
{
    if(phead == NULL)
        return NULL;

    LinkNode* slow = phead;
    LinkNode* fast = phead;
    while(fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return slow;
        }
    }
    return NULL;
}
//求环的长度
int LinkListCycleLen(LinkNode* phead)
{
    if(phead == NULL)
    {
        return 0;
    }
    //记录快慢指针相遇的位置
    LinkNode* meet_node = LinkListHasCycle(phead);
    if(meet_node == NULL)
    {
        return 0;
    }
    //记录下相遇位置的下一个，等再回到该位置，走了几步环就有多长
    LinkNode* cur = meet_node->next;
    int Len = 1;
    while(cur != meet_node)
    {
        cur = cur->next;
        ++Len;
    }
    return Len;
}

//求环的入口点
LinkNode* LinkListCycleEntry(LinkNode* phead)
{
    if(phead == NULL)
    {
        return NULL;
    }

    LinkNode* meet_node = LinkListHasCycle(phead);
    if(meet_node == NULL)
    {
        return NULL;
    }
    //定义cur1指向头结点，cur2指向相遇的位置
    LinkNode* cur1 = phead;
    LinkNode* cur2 = meet_node;
    while(cur1 != cur2)
    {
    //cur1和cur2每次各走一步，直到它俩相遇，相遇的位置就是入口点
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return cur1;
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337

判断两个链表是否相交
这里写图片描述
思路：让cur1走到最后一个节点，再让cur2也走向最后一个节点，如果两个相等，说明cur1和cur2相交

//判断两个链表是否相交
int LinkListCross(LinkNode* head1,LinkNode* head2)
{
    if(head1 == NULL||head2 == NULL)
    {
        return 0;
    }
    //1.定义cur1指向head1;
    LinkNode* cur1 = head1;
    //2.让cur1遍历链表head1,走到最后一个节点
    while(cur1->next != NULL)
    {
        cur1 = cur1->next;
    }
    //3.定义cur2指向head2;
    LinkNode* cur2 = head2;
    //4.让cur2遍历链表head2，走到最后一个节点
    while(cur2->next != NULL)
    {
        cur2 = cur2->next;
    }
    //5.判断，如果此时cur1和cur2相等，则相交；否则，不相交
    if(cur1 == cur2)
    {
        return 1;
    }
    else
    {

        return 0;
    }
}
//求交点
LinkNode* LinkListHasCross(LinkNode* head1,LinkNode* head2)
{
    if(head1 == NULL||head2 == NULL)
    {
        return NULL;
    }
    //1.分别计算两个链表的长度
    int len1 = LinkListSize(head1);
    int len2 = LinkListSize(head2);
    //2.定义两个指针分别指向两个链表的头部
    LinkNode* cur1 = head1;
    LinkNode* cur2 = head2;
    //3.让比较长的链表先走长度之差步（让两个指针在统一起跑线）
    if(len1 > len2)
    {
        size_t i = 0;
        for( ;i < len1-len2;++i)
        {
            cur1 = cur1->next;
        }
    }
    else
    {
        size_t i = 0;
        for( ;i < len2-len1;++i)
        {
            cur2 = cur2->next;
        }
    }
    //4.让两个指针同时开始走，一次走一步
    //5.如果两指针重合，则说明此位置就是交点
    while(cur1 != NULL && cur2 != NULL)
    {
        if(cur1 == cur2)
        {
            return cur1;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return NULL;

}
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

判断两个链表是否相交，相交，若相交，求交点（链表可能带环）
带环的四种情况：
这里写图片描述


int LinkListCrossWithCycle(LinkNode* head1,LinkNode* head2)
{
    //1.分别求两个链表的环的入口点
    LinkNode* entry1 = LinkListCycleEntry(head1);
    LinkNode* entry2 = LinkListCycleEntry(head2);
    //2.如果两个链表都不带环，直接用前面的方式判定相交
    if(entry1 == NULL && entry2 == NULL)
    {
        return LinkListCross(head1,head2);
    }
    //3.如果一个带环，一个不带环，那么直接返回不相交
    if((entry1 == NULL && entry2 != NULL)||(entry1 != NULL && entry2 == NULL))
    {
        return 0;
    }
    //4.如果两个链表都带环
    //   a)如果这两个入口点重合，说明相交，并且是环外相交
    if(entry1 == entry2)
    {
        return 1;
    }
    //   b)如果从一个入口点出发，绕环一周，能到达第二个入口点，说明是环上相交
    LinkNode* cur = entry1->next;
    while(cur != entry1)
    {
        if(cur == entry2)
        {
            return 1;
        }
        cur = cur->next;
    }
    //   c)如果不是上面这两种情况，说明不相交
    return 0;
}

//求交点
LinkNode* LinkListHasCrossWithCycle(LinkNode* head1,LinkNode* head2)
{
    if(head1 == NULL||head2 == NULL)
    {
        return NULL;
    }
    int i = LinkListCrossWithCycle(head1,head2);
    if(i == 0)
    {
       return NULL;
    }
    //1.求环的入口点
    LinkNode* entry1 = LinkListCycleEntry(head1);
    LinkNode* entry2 = LinkListCycleEntry(head2);
    //2.判断是那种情况相交
    if(entry1 != entry2)//环上相交
    {
        return entry2;
    }
    //3.标记入口点
    LinkNode* end = entry1;
    //4.另一种情况，环外相交，分别计算两个链表头到入口点的长度
    //5.定义两个指针分别指向两个链表的头部
    int len1 = 0;
    int len2 = 0;
    LinkNode* cur1 = head1;
    LinkNode* cur2 = head2;
    for( ;cur1 != end;cur1 = cur1->next)
    {
         len1++;
    }
    for( ;cur2 != end;cur2 = cur2->next)
    {
         len2++;
    }
    //6.让比较长的链表先走长度之差步（让两个指针在统一起跑线）
    if(len1 > len2)
    {
        size_t i = 0;
        for( ;i < len1-len2;++i)
        {
            cur1 = cur1->next;
        }
    }
    else
    {
        size_t i = 0;
        for( ;i < len2-len1;++i)
        {
            cur2 = cur2->next;
        }
    }
    //7.让两个指针同时开始走，一次走一步
    //8.如果两指针重合，则说明此位置就是交点
    while(cur1 != end->next && cur2 != end->next)
    {
        if(cur1 == cur2)
        {
            return cur1;
        }
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return NULL;

}
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

求两个已排序单链表中相同的数据
这里写图片描述
思路：遍历两个链表，cur1指向head1，cur2指向head2,如果两个元素相等，则重新创建一个结点，值等于该元素，并将其插入到新链表中；如果不相等，则更新两个指针

LinkNode* LinkListUnionSet(LinkNode* head1,LinkNode* head2)
{
    if(head1 == NULL || head2  == NULL)
    {
        return NULL;
    }
    LinkNode* cur1 = head1;
    LinkNode* cur2 = head2;

    LinkNode* new_head = NULL;
    LinkNode* new_tail = NULL;
    while(cur1 != NULL && cur2 != NULL)
    {
        if(cur1->data < cur2->data)
        {
            cur1 = cur1->next;
        }
        else if(cur1->data > cur2->data)
        {
            cur2 = cur2->next;
        }
        else
        {
            if(new_head == NULL)
            {
                new_head = new_tail = CreateNode(cur1->data);
            }
            else
            {
                new_tail->next = CreateNode(cur1->data);
                new_tail =new_tail->next;
            }

            cur1 = cur1->next;
            cur2 = cur2->next;
        }
    }
    return new_head;
}
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

复杂链表的复制，复杂链表相比较普通链表多了一个random指针，而这个指针的指向是任意的，所以复制的难点就在于如何让新链表的random指针保持和旧链表的一致性，有两种思路：
一种是先忽略random指针，按简单链表的方式进行复制，然后求得random指针相对于头结点的偏移量，最后在新链表里根据偏移量进行设置。
第二种是遍历链表，给每个结点后插入一个新的结点，这个新结点值和它的前一个元素相等，新结点的random指针就等于旧结点random指针的下一个，最后再将新结点拆除。

typedef struct ComplexNode
{
    LinkNodeType data;
    struct ComplexNode* next;
    struct ComplexNode* random;
}ComplexNode;
//创建复杂结点
ComplexNode* CreateComplexNode(LinkNodeType value)
{
    ComplexNode* new_node = (ComplexNode*)malloc(sizeof(ComplexNode));
    new_node->data = value;
    new_node->next = NULL;
    new_node->random = NULL;
    return new_node;
}
//求偏移量
size_t Diff(ComplexNode* src,ComplexNode* dest)
{
    size_t offset = 0;
    while(src != NULL)
    {
        if(src == dest)
        {
            break;
        }
        offset++;
        src = src->next;
    }
    if(src == NULL)
    {
        return (size_t)-1;
    }
    return offset;

}
//设置random指针
ComplexNode* Step(ComplexNode* head,size_t offset)
{
    ComplexNode* cur = head;
    size_t i = 0;
    while(1)
    {
        if(cur == NULL)
        {
            return NULL;
        }
        if(i >= offset)
        {
            return cur;
        }
        ++i;
        cur = cur->next;    
    }
    return cur;
}
ComplexNode* CopyComplexList(ComplexNode* head)
{
    //1.先按照简单链表的方式进行复制
    ComplexNode* new_head = NULL;
    ComplexNode* new_tail = NULL;
    ComplexNode* cur = head;
    for( ;cur != NULL;cur = cur->next)
    {
        ComplexNode* new_node = CreateComplexNode(cur->data);
        if(new_head == NULL)
        {
            new_head = new_tail = new_node;
        }
        else
        {
            new_tail->next = new_node;
            new_tail = new_tail->next;
        }
    }
    //2.遍历旧链表，找到每个链表节点的random指针相对于链表头节点的偏移量
    //3.遍历新链表，根据偏移量，设置新链表的random指针
    ComplexNode* new_cur = new_head;
    for(cur = head;cur != NULL;cur = cur->next,new_cur = new_cur->next)
    {
        if(cur->random == NULL)
        {
            new_cur->random = NULL;
                continue;
        }
        //通过Diff函数找到random的偏移量
        size_t offset = Diff(head,cur->random);
        //通过Step函数设置新链表的Random指针
        new_cur->random = Step(new_head,offset);
    }
    return new_head;
}

ComplexNode* CopyComplexList2(ComplexNode* head)
{
    //1.遍历链表，给每个结点之后插入新结点
    ComplexNode* cur = head;
    for( ;cur != NULL;cur = cur->next->next)
    {
        ComplexNode* new_node = CreateComplexNode(cur->data);
        new_node->next = cur->next;
        cur->next = new_node;
    }
    //2.维护新结点的randon指针
    for(cur = head;cur != NULL;cur = cur->next->next)
    {
        ComplexNode* new_cur = cur->next;
        if(cur->random == NULL)
        {
            new_cur->random = NULL;
            continue;
        }
        new_cur->random = cur->random->next;
    }
    //3.将新结点拆除
    ComplexNode* new_head = NULL;
    ComplexNode* new_tail = NULL;
    for(cur = head;cur != NULL;cur = cur->next)
    {
        ComplexNode* new_cur = cur->next;
        cur->next = new_cur->next;
        if(new_head == NULL)
        {
            new_head = new_tail = new_cur;
        }
        else
        {
            new_tail->next = new_cur;
            new_tail = new_tail->next;
        }
    }

    return new_head;
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

3.测试代码：

#define TEST_HEADER printf("\n=====================%s====================\n",__FUNCTION__)

void LinkListPrintChar(LinkNode* head,const char* msg)
{
    printf("[%s]\n",msg);
    LinkNode* cur = head;
    for( ;cur != NULL;cur = cur->next)
    {
        printf("[%c|%p] ",cur->data,cur);
    }
    printf("\n");

}
void TestReversePrint()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    printf("[逆序打印链表]\n");
    LinkListReversePrint(head);
}

void TestReverse()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListReverse(&head);
    LinkListPrintChar(head,"尝试对空链表操作");

    LinkListPushBack(&head,'a');
    LinkListReverse(&head);
    LinkListPrintChar(head,"对只有一个元素的链表逆序");

    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListReverse(&head);
    LinkListPrintChar(head,"逆序链表");
}
void TestReverse2()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListReverse2(&head);
    LinkListPrintChar(head,"尝试对空链表操作");

    LinkListPushBack(&head,'a');
    LinkListReverse2(&head);
    LinkListPrintChar(head,"对只有一个元素的链表逆序");

    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListReverse2(&head);
    LinkListPrintChar(head,"逆序链表");
}

void TestJosephCircle()
{
    TEST_HEADER;
    LinkNode* a = CreateNode('a');
    LinkNode* b = CreateNode('b');
    LinkNode* c = CreateNode('c');
    LinkNode* d = CreateNode('d');
    LinkNode* e = CreateNode('e');
    LinkNode* f = CreateNode('f');
    LinkNode* g = CreateNode('g');
    LinkNode* h = CreateNode('h');
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = e;
    e->next = f;
    f->next = g;
    g->next = h;
    h->next = a;

    LinkNode* survive = JosephCircle(a,5);
    printf("survive is %c\n",survive->data);
}

void TestBubbleSort()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'f');
    LinkListPushBack(&head,'e');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'g');
    LinkListPushBack(&head,'h');
    LinkListPushBack(&head,'d');

    LinkListBubbleSort(head);
    LinkListPrintChar(head,"冒泡排序");
}
void TestMerge()
{
    TEST_HEADER;
    LinkNode* head1;
    LinkNode* head2;
    LinkNode* head3;
    LinkListInit(&head1);
    LinkListInit(&head2);
    LinkListInit(&head3);

    LinkListPushBack(&head1,'a');
    LinkListPushBack(&head1,'b');
    LinkListPushBack(&head1,'c');
    LinkListPushBack(&head1,'d');
    LinkListPushBack(&head2,'e');
    LinkListPushBack(&head2,'f');
    LinkListPushBack(&head2,'g');
    LinkListPushBack(&head2,'h');

    head3 = LinkListMerge(head1,head2);
    LinkListPrintChar(head3,"将已经有序的两个链表合并成一个有序链表");
}

void TestFindMidNode()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* Mid = LinkListFindMidNode(head);
    LinkListPrintChar(head,"查找链表的中间节点");
    printf("Mid expected is c,actual is %c\n ",Mid->data);
}

void TestFindLastKNode()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* LastK = LinkListFindLastKNode(head,2);
    LinkListPrintChar(head,"查找链表的倒数第2个节点");
    printf("Mid expected is d,actual is %c\n ",LastK->data);
}

void TestEraseLastKNode()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkListEraseLastKNode(&head,2);
    LinkListPrintChar(head,"删除链表的倒数第2个节点");
}

void TestHasCycle()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* pos_e = LinkListFind(head,'e');
    pos_e->next =head->next->next;

    LinkNode* meet_node= LinkListHasCycle(head);

    printf("meet_node expected is d,actual is %c\n",meet_node->data);
}

void TestCycleLen()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* pos_e = LinkListFind(head,'e');
    pos_e->next =head->next->next;

    int len= LinkListCycleLen(head);
    printf("len expected is 3,actual is %d\n",len);
}

void TestCycleEntry()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);

    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* pos_e = LinkListFind(head,'e');
    pos_e->next =head->next->next;

    LinkNode* entry_node = LinkListCycleEntry(head);
    printf("entry_node expected is c,actual is %c\n",entry_node->data);
}

void TestCross()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* head2;
    LinkListInit(&head2);
    LinkListPushBack(&head2,'a');
    LinkListPushBack(&head2,'b');
    LinkListPushBack(&head2,'c');
    LinkNode* pos_c = LinkListFind(head2,'c');
    pos_c->next = head->next;

    int ret = LinkListCross(head,head2);
    printf("ret excepted is 1,actual is %d\n",ret);
}

void TestHasCross()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* head2;
    LinkListInit(&head2);
    LinkListPushBack(&head2,'a');
    LinkListPushBack(&head2,'b');
    LinkListPushBack(&head2,'c');
    LinkNode* pos_c = LinkListFind(head2,'c');
    pos_c->next = head->next;

    LinkNode* cross = LinkListHasCross(head,head2);
    printf("cross expected is b,actual is %c\n",cross->data);
}

void TestCrossWithCycle()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* head1;
    LinkListInit(&head1);
    LinkListPushBack(&head1,'a');
    LinkListPushBack(&head1,'b');
    LinkListPushBack(&head1,'c');
    LinkListPushBack(&head1,'d');

    int ret1 = LinkListCrossWithCycle(head,head1);
    printf("[两个链表都不带环]\n");
    printf("ret1 expected is 0,actual is %d\n",ret1);

    LinkNode* head2;
    LinkListInit(&head2);   
    LinkListPushBack(&head2,'a');
    LinkListPushBack(&head2,'b');
    LinkListPushBack(&head2,'c');
    LinkListPushBack(&head2,'d');
    LinkListPushBack(&head2,'e');
    LinkNode* pos_e = LinkListFind(head2,'e');
    pos_e->next =head2->next->next;

    LinkNode* head3;
    LinkListInit(&head3);   
    LinkListPushBack(&head3,'a');
    LinkListPushBack(&head3,'b');
    LinkListPushBack(&head3,'c');
    LinkListPushBack(&head3,'d');
    LinkListPushBack(&head3,'e');
    LinkNode* pos_2e = LinkListFind(head3,'e');
    pos_2e->next =head3->next;

    int ret2 = LinkListCrossWithCycle(head2,head3);
    printf("[两个链表都带环]\n");
    printf("ret2 expected is 0,actual is %d\n",ret2);

    LinkNode* head4;
    LinkListInit(&head4);
    LinkListPushBack(&head4,'a');
    LinkListPushBack(&head4,'b');
    LinkListPushBack(&head4,'c');
    LinkNode* pos_c = LinkListFind(head4,'c');
    pos_c->next = head2->next;

    int ret3 = LinkListCrossWithCycle(head2,head4);
    printf("[两个链表都带环，满足a情况]\n");
    printf("ret3 expected is 1,actual is %d\n",ret3);

    LinkNode* head5;
    LinkListInit(&head5);
    LinkListPushBack(&head5,'a');
    LinkListPushBack(&head5,'b');
    LinkListPushBack(&head5,'c');
    LinkListPushBack(&head5,'d');
    LinkNode* pos_d = LinkListFind(head5,'d');
    pos_d->next =head2->next->next->next;

    int ret4 = LinkListCrossWithCycle(head2,head5);
    printf("[两个链表都带环，满足b情况]\n");
    printf("ret4 expected is 1,actual id %d\n",ret4);
}

void TestHasCrossWithCycle()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');    
    LinkNode* pos_e = LinkListFind(head,'e');
    pos_e->next =head->next->next;

    LinkNode* head1;
    LinkListInit(&head1);
    LinkListPushBack(&head1,'a');
    LinkListPushBack(&head1,'b');
    LinkListPushBack(&head1,'c');
    LinkListPushBack(&head1,'d');
    LinkNode* pos_d = LinkListFind(head1,'d');
    pos_d->next = head->next;

    LinkNode* cross = LinkListHasCrossWithCycle(head,head1);
    printf("[两个链表都带环，环外相交]\n");
    printf("cross expected c,actual %c\n",cross->data);

    LinkNode* head2;
    LinkListPushBack(&head2,'a');
    LinkListPushBack(&head2,'b');
    LinkListPushBack(&head2,'c');
    LinkListPushBack(&head2,'d');
    LinkNode* pos_d2 = LinkListFind(head2,'d');
    pos_d2->next =head->next->next->next;

    LinkNode* cross2 = LinkListHasCrossWithCycle(head,head2);
    printf("[两个链表都带环，入口点就是交点]\n");
    printf("cross2 expected c或者d,actual %c\n",cross2->data);
}
void TestUnionSet()
{

    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    LinkListPushBack(&head,'a');
    LinkListPushBack(&head,'b');
    LinkListPushBack(&head,'c');
    LinkListPushBack(&head,'d');
    LinkListPushBack(&head,'e');

    LinkNode* head1;
    LinkListInit(&head1);
    LinkListPushBack(&head1,'a');
    LinkListPushBack(&head1,'c');
    LinkListPushBack(&head1,'e');
    LinkListPushBack(&head1,'f');
    LinkListPushBack(&head1,'h');
    LinkNode* union_set = LinkListUnionSet(head,head1);
    LinkListPrintChar(union_set,"链表的交集是：");
}

void PrintComplexList(ComplexNode* head,const char* msg)
{
    printf("[%s]\n",msg);
    ComplexNode* cur = head;
    for( ;cur != NULL;cur = cur->next)
    {
        printf("[%c]",cur->data);
    }
    printf("\n");
    for(cur = head ;cur != NULL;cur = cur->next)
    {
        if(cur->random == NULL)
        {
            printf("[NULL]");
            continue;
        }
        printf("[%c]",cur->random->data);
    }
    printf("\n");
}
void TestCopyComplexList()
{
    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    ComplexNode* a = CreateComplexNode('a');
    ComplexNode* b = CreateComplexNode('b');
    ComplexNode* c = CreateComplexNode('c');
    ComplexNode* d = CreateComplexNode('d');
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = NULL;
    a->random = c;
    b->random = a;
    c->random = NULL;
    d->random = d;

    ComplexNode*  new_head= CopyComplexList(a);
    PrintComplexList(new_head,"复杂链表的复制");
}

void TestCopyComplexList2()
{
    TEST_HEADER;
    LinkNode* head;
    LinkListInit(&head);
    ComplexNode* a = CreateComplexNode('a');
    ComplexNode* b = CreateComplexNode('b');
    ComplexNode* c = CreateComplexNode('c');
    ComplexNode* d = CreateComplexNode('d');
    a->next = b;
    b->next = c;
    c->next = d;
    d->next = NULL;
    a->random = c;
    b->random = a;
    c->random = NULL;
    d->random = d;

    ComplexNode*  new_head = CopyComplexList2(a);
    PrintComplexList(new_head,"复杂链表的复制");
}
int main()
{
    TestReversePrint();
    TestReverse();
    TestReverse2();
    TestJosephCircle();
    TestBubbleSort();
    TestMerge();
    TestFindMidNode();
    TestFindLastKNode();
    TestEraseLastKNode();
    TestHasCycle();
    TestCycleLen();
    TestCycleEntry();
    TestCross();
    TestHasCross();
    TestCrossWithCycle();
    TestHasCrossWithCycle();
    TestUnionSet();
    TestCopyComplexList();
    TestCopyComplexList2();
    printf("\n");
    return 0;
}
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】

数据结构-链表的经典面试题_数据结构 单链表 面试

数据结构-链表的经典面试题_数据结构单链表面试