链表OJ题

文章目录

• • 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 #include 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 #include 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 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 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 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 #include 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 #include 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;}