链表OJ题

1. 链表的回文布局

由于单链表不能从后往前找节点，以是我们先找到中间节点，然后逆置，最后进行比力。

1. #include <stdio.h>
2. #include <stdbool.h>
4. typedef struct ListNode
5. {
6.         int val;
7.         struct ListNode* next;
8. }ListNode;
10. struct ListNode* middleNode(struct ListNode* head)
11. {
12.         ListNode* slow, * fast;
13.         slow = fast = head;
15.         while (fast && fast->next)
16.         {
17.                 slow = slow->next;
18.                 fast = fast->next->next;
19.         }
21.         return slow;
22. }
24. struct ListNode* reverseList(struct ListNode* head)
25. {
26.         if (NULL == head)
27.         {
28.                 return head;
29.         }
31.         ListNode* n1, * n2, * n3;
32.         n1 = NULL, n2 = head, n3 = head->next;
34.         while (n2)
35.         {
36.                 n2->next = n1;
37.                 n1 = n2;
38.                 n2 = n3;
40.                 if (n3)
41.                 {
42.                         n3 = n3->next;
43.                 }
44.         }
46.         return n1;
47. }
49. bool chkPalindrome(ListNode* A)
50. {
51.         ListNode* mid = middleNode(A);
52.         ListNode* rmid = reverseList(mid);
54.         while (A && rmid)
55.         {
56.                 if (A->val != rmid->val)
57.                 {
58.                         return false;
59.                 }
61.                 A = A->next;
62.                 rmid = rmid->next;
63.         }
65.         return true;
66. }

复制代码

2. 相交链表

1. #include <stdio.h>
2. #include <stdlib.h>
4. struct ListNode
5. {
6.         int val;
7.         struct ListNode* next;
8. };
10. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
11. {
12.         struct ListNode* curA = headA;
13.         struct ListNode* curB = headB;
15.         int lenA = 0;
17.         while (curA->next)
18.         {
19.                 ++lenA;
20.                 curA = curA->next;
21.         }
22.        
23.         int lenB = 0;
25.         while (curB->next)
26.         {
27.                 ++lenB;
28.                 curB = curB->next;
29.         }
31.         //不相交
32.         if (curA != curB)
33.         {
34.                 return NULL;
35.         }
37.         int gap = abs(lenA - lenB);
38.         //因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行
39.         struct ListNode* longList = headA;
40.         struct ListNode* shortList = headB;
42.         if (lenB > lenA)
43.         {
44.                 longList = headB;
45.                 shortList = headA;
46.         }
48.         //让长的先走gap步
49.         while (gap--)
50.         {
51.                 longList = longList->next;
52.         }
54.         //再同时走，找交点
55.         while (longList != shortList)
56.         {
57.                 longList = longList->next;
58.                 shortList = shortList->next;
59.         }
61.         return longList;
62. }

复制代码

3. 链表中倒数第k个结点

思路2：

1. #include <stdio.h>
3. struct ListNode
4. {
5.         int val;
6.         struct ListNoe* next;
7. };
9. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
10. {
11.         struct ListNode* slow = pListHead, * fast = pListHead;
13.         //fast先走k步
14.         while (k--)
15.         {
16.                 //k还没有减到0，链表已经空了，说明k大于链表的长度
17.                 if (NULL == fast)
18.                 {
19.                         return NULL;
20.                 }
22.                 fast = fast->next;
23.         }
25.         //slow和fast同时走，fast走到空，slow就是倒数第k个
26.         while (fast)
27.         {
28.                 slow = slow->next;
29.                 fast = fast->next;
30.         }
32.         return slow;
33. }

复制代码

4. 环形链表

1. #include <stdbool.h>
3. struct ListNode
4. {
5.         int val;
6.         struct ListNode* next;
7. };
10. bool hasCycle(struct ListNode* head)
11. {
12.         struct ListNode* slow = head, * fast = head;
14.         while (fast && fast->next)
15.         {
16.                 slow = slow->next;
17.                 fast = fast->next->next;
19.                 if (slow == fast)
20.                 {
21.                         return true;
22.                 }
23.         }
25.         return false;
26. }

复制代码

5. 环形链表 II

找入环点：

法一：

1. #include <stdio.h>
3. struct ListNode
4. {
5.         int val;
6.         struct ListNode* next;
7. };
9. struct ListNode* detectCycle(struct ListNode* head)
10. {
11.         struct ListNode* slow = head, * fast = head;
13.         while (fast && fast->next)
14.         {
15.                 slow = slow->next;
16.                 fast = fast->next->next;
18.                 if (slow == fast)
19.                 {
20.                         struct ListNode* meet = slow;
22.                         while (meet != head)
23.                         {
24.                                 meet = meet->next;
25.                                 head = head->next;
26.                         }
28.                         return meet;
29.                 }
30.         }
32.         return NULL;
33. }

复制代码

法二：

1. #include <stdio.h>
2. #include <stdlib.h>
4. struct ListNode
5. {
6.         int val;
7.         struct ListNode* next;
8. };
10. struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
11. {
12.         struct ListNode* curA = headA;
13.         struct ListNode* curB = headB;
15.         int lenA = 0;
17.         while (curA->next)
18.         {
19.                 ++lenA;
20.                 curA = curA->next;
21.         }
23.         int lenB = 0;
25.         while (curB->next)
26.         {
27.                 ++lenB;
28.                 curB = curB->next;
29.         }
31.         //不相交
32.         if (curA != curB)
33.         {
34.                 return NULL;
35.         }
37.         int gap = abs(lenA - lenB);
38.         struct ListNode* longList = headA;
39.         struct ListNode* shortList = headB;
41.         if (lenB > lenA)
42.         {
43.                 longList = headB;
44.                 shortList = headA;
45.         }
47.         //让长的先走gap步
48.         while (gap--)
49.         {
50.                 longList = longList->next;
51.         }
53.         //再同时走，找交点
54.         while (longList != shortList)
55.         {
56.                 longList = longList->next;
57.                 shortList = shortList->next;
58.         }
60.         return longList;
61. }
63. struct ListNode* detectCycle(struct ListNode* head)
64. {
65.         struct ListNode* slow = head, * fast = head;
67.         while (fast && fast->next)
68.         {
69.                 slow = slow->next;
70.                 fast = fast->next->next;
72.                 if (slow == fast)
73.                 {
74.                         struct ListNode* meet = slow;
75.                         struct ListNode* headx = meet->next;
76.                         meet->next = NULL;
78.                         return getIntersectionNode(head, headx);
79.                 }
80.         }
82.         return NULL;
83. }

复制代码

6. 随机链表的复制

写代码的时候建议一边画细图，一边写：

1. #include <stdio.h>
2. #include <stdlib.h>
4. struct Node
5. {
6.     int val;
7.     struct Node *next;
8.     struct Node *random;
9. };
11. struct Node* copyRandomList(struct Node* head)
12. {
13.     struct Node* cur = head;
15.     //拷贝节点插入原节点的后面
17.     while (cur)
18.     {
19.         struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
20.         copy->val = cur->val;
22.         //插入
23.         copy->next = cur->next;
24.         cur->next = copy;
26.         //迭代
27.         cur = cur->next->next;
28.     }
30.     //控制拷贝节点的random
31.     cur = head;
33.     while (cur)
34.     {
35.         struct Node* copy = cur->next;
36.         
37.         if (NULL == cur->random)
38.         {
39.             copy->random = NULL;
40.         }
41.         else
42.         {
43.             copy->random = cur->random->next;
44.         }
46.         //迭代
47.         cur = cur->next->next;
48.     }
50.     //把copy节点解下来，链接成新链表
51.     struct Node* copyhead = NULL, * tail = NULL;
52.     cur = head;
54.     while (cur)
55.     {
56.         struct Node* copy = cur->next;
57.         struct Node* next = copy->next;
59.         //尾插
60.         if (NULL == tail)
61.         {
62.             copyhead = tail = copy;
63.         }
64.         else
65.         {
66.             tail->next = copy;
67.             tail = tail->next;
68.         }
70.         cur->next = next;
71.         cur = next;
72.     }
74.     return copyhead;
75. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。