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; }
