文章目录

1. [链表的回文结构](https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking)2. [相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)3. 链表中倒数第k个结点4. [环形链表](https://leetcode.cn/problems/linked-list-cycle/description/)5. [环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/description/)6. [随机链表的复制](https://leetcode.cn/problems/copy-list-with-random-pointer/description/)

1. 链表的回文结构

因为单链表不能从后往前找节点，所以我们先找到中间节点，然后逆置，最后进行比较。

#include <stdio.h>#include <stdbool.h>typedef struct ListNode{ int val;struct ListNode* next;}ListNode;struct ListNode* middleNode(struct ListNode* head){ ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){ slow = slow->next;fast = fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head){ if (NULL == head){ return head;}ListNode* n1, * n2, * n3;n1 = NULL, n2 = head, n3 = head->next;while (n2){ n2->next = n1;n1 = n2;n2 = n3;if (n3){ n3 = n3->next;}}return n1;}bool chkPalindrome(ListNode* A){ ListNode* mid = middleNode(A);ListNode* rmid = reverseList(mid);while (A && rmid){ if (A->val != rmid->val){ return false;}A = A->next;rmid = rmid->next;}return true;}

2. 相交链表

#include <stdio.h>#include <stdlib.h>struct ListNode{ int val;struct ListNode* next;};struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB){ struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 0;while (curA->next){ ++lenA;curA = curA->next;}int lenB = 0;while (curB->next){ ++lenB;curB = curB->next;}//不相交if (curA != curB){ return NULL;}int gap = abs(lenA - lenB);//因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lenB > lenA){ longList = headB;shortList = headA;}//让长的先走gap步while (gap--){ longList = longList->next;}//再同时走，找交点while (longList != shortList){ longList = longList->next;shortList = shortList->next;}return longList;}

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

思路2：

#include <stdio.h>struct ListNode{ int val;struct ListNoe* next;};struct ListNode* FindKthToTail(struct ListNode* pListHead, int k){ struct ListNode* slow = pListHead, * fast = pListHead;//fast先走k步while (k--){ //k还没有减到0，链表已经空了，说明k大于链表的长度if (NULL == fast){ return NULL;}fast = fast->next;}//slow和fast同时走，fast走到空，slow就是倒数第k个while (fast){ slow = slow->next;fast = fast->next;}return slow;}

4. 环形链表

#include <stdbool.h>struct ListNode{ int val;struct ListNode* next;}; bool hasCycle(struct ListNode* head){ struct ListNode* slow = head, * fast = head;while (fast && fast->next){ slow = slow->next;fast = fast->next->next;if (slow == fast){ return true;}}return false;}

5. 环形链表 II

找入环点：

法一：

#include <stdio.h>struct ListNode{ int val;struct ListNode* next;};struct ListNode* detectCycle(struct ListNode* head){ struct ListNode* slow = head, * fast = head;while (fast && fast->next){ slow = slow->next;fast = fast->next->next;if (slow == fast){ struct ListNode* meet = slow;while (meet != head){ meet = meet->next;head = head->next;}return meet;}}return NULL;}

法二：

#include <stdio.h>#include <stdlib.h>struct ListNode{ int val;struct ListNode* next;};struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB){ struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 0;while (curA->next){ ++lenA;curA = curA->next;}int lenB = 0;while (curB->next){ ++lenB;curB = curB->next;}//不相交if (curA != curB){ return NULL;}int gap = abs(lenA - lenB);struct ListNode* longList = headA;struct ListNode* shortList = headB;if (lenB > lenA){ longList = headB;shortList = headA;}//让长的先走gap步while (gap--){ longList = longList->next;}//再同时走，找交点while (longList != shortList){ longList = longList->next;shortList = shortList->next;}return longList;}struct ListNode* detectCycle(struct ListNode* head){ struct ListNode* slow = head, * fast = head;while (fast && fast->next){ slow = slow->next;fast = fast->next->next;if (slow == fast){ struct ListNode* meet = slow;struct ListNode* headx = meet->next;meet->next = NULL;return getIntersectionNode(head, headx);}}return NULL;}

6. 随机链表的复制

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

#include <stdio.h>#include <stdlib.h>struct Node{ int val; struct Node *next; struct Node *random;};struct Node* copyRandomList(struct Node* head){ struct Node* cur = head; //拷贝节点插入原节点的后面 while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //插入 copy->next = cur->next; cur->next = copy; //迭代 cur = cur->next->next; } //控制拷贝节点的random cur = head; while (cur) { struct Node* copy = cur->next; if (NULL == cur->random) { copy->random = NULL; } else { copy->random = cur->random->next; } //迭代 cur = cur->next->next; } //把copy节点解下来，链接成新链表 struct Node* copyhead = NULL, * tail = NULL; cur = head; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //尾插 if (NULL == tail) { copyhead = tail = copy; } else { tail->next = copy; tail = tail->next; } cur->next = next; cur = next; } return copyhead;}