抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的链表问题~
参考链接：leetcode 剑指offer
概述
- 涉及到删除、插入等问题的一般需要添加dummyHead
- 若对链表中的某一段进行处理，且处理后需要把这一段接回原链表：一定要用last记录被处理的那段的最后一个节点，并把它接回原链表
- 只要有p->next，一定要保证p不为空
反转链表相关题目
完全反转链表
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* dummyHead = new ListNode(-1);
ListNode* prev = dummyHead;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
}
return dummyHead->next;
}
每k个反转链表（lc25）
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k <= 1) return head;
ListNode* dummyHead = new ListNode(-1);
ListNode* prev = dummyHead; // k个一组的组头的前面那个
prev->next = head;
ListNode* cur = head; // k个一组的组头
for (int i = 1; cur; ++i) { // i从1开始！
if (i % k == 0) {
prev = reverseOneGroup(prev, cur->next);
cur = prev->next;
} else {
cur = cur->next;
}
}
return dummyHead->next;
}
ListNode* reverseOneGroup(ListNode* pre, ListNode* end) { // 反转pre->next到end（不含end）的节点；返回反转后的组尾
ListNode* cur = pre->next->next;
ListNode* last = pre->next;
while (cur != end) {
last->next = cur->next; // 注意这里！需要把这组和原链表连起来！
cur->next = pre->next;
pre->next = cur;
cur = last->next;
}
return last;
}
};
反转链表的第m-n个（lc92）
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == nullptr) return head;
ListNode* dummyHead = new ListNode(-1);
dummyHead->next = head;
ListNode* cur = head;
ListNode* prev = dummyHead;
int i = 1;
while (i < m) {
prev = prev->next;
cur = cur->next;
++i;
}
ListNode* last = cur;
cur = cur->next;
while (i < n) {
ListNode* next = cur->next;
cur->next = prev->next;
prev->next = cur;
cur = next;
++i;
}
last->next = cur; // 注意这里！需要把这组和原链表连起来！
return dummyHead->next;
}
删除重复元素
重复的元素不保留（lc82）
- 法一：从头到尾遍历：prev记录start前的那个节点；start记录最开始的重复元素；cur记录现在遍历到的元素
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode* dummyHead = new ListNode(-1);
ListNode* prev = dummyHead;
prev->next = head;
ListNode* start = head;
ListNode* cur = start->next;
int cnt = 1;
while (cur) {
if (cur->val == start->val) {
cur = cur->next;
++cnt;
} else {
if (cnt > 1) prev->next = cur;
else prev = start;
start = cur;
cur = cur->next;
cnt = 1;
}
}
if (cnt > 1) prev->next = nullptr;
return dummyHead->next;
}
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
if (head->next && head->val == head->next->val) {
while (head->next && head->val == head->next->val) {
head = head->next;
}
return deleteDuplicates(head->next);
}
head->next = deleteDuplicates(head->next);
return head;
}
重复的元素只保留一个（lc83）
- 法一：遍历并删除：start记录最开始的重复元素；cur记录现在遍历到的元素
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
ListNode *start = head, *cur = head->next;
bool flag = false;
while (cur) {
if (cur->val == start->val) {
cur = cur->next;
flag = true;
} else {
start->next = cur;
start = start->next;
cur = start->next;
flag = false;
}
}
if (flag) start->next = nullptr;
return head;
}
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) return head;
head->next = deleteDuplicates(head->next);
return (head->val == head->next->val) ? head->next : head;
}
链表环
求环入口（jz55）
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if (!pHead || !pHead->next) return NULL;
ListNode* fast = pHead->next->next;
ListNode* slow = pHead->next; // 注意是head->next而不是head！
while (slow != fast) {
if (!fast || !fast->next) return NULL;
fast = fast->next->next;
slow = slow->next;
}
fast = pHead;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
判断是否有环（lc141）
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;
ListNode* slow = head->next;
ListNode* fast = head->next->next;
while (fast != slow) {
slow = slow->next;
if (!fast || !fast->next) return false;
fast = fast->next->next;
}
return true;
}
其他题目
从中间拆分链表
void splitList(ListNode* head) { // 第一段链表长度<=第二段链表长度，即拆分点在中间偏左的位置
if (!head || !head->next) return;
ListNode* slow = head;
ListNode* fast = head->next->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* fast = slow->next; // 第二段链表从fast开始到最后
slow->next = nullptr; // 第一段链表从head开始到slow
}
链表排序（lc148）
- 思路：先把链表从中间断开，分别sort链表，再merge两个链表
- 注意：merge(sortList(head), sortList(slow))
重排链表（lc143）
- 思路：先把链表从中间断开，再反转后半段，再merge
获取倒数第k个节点
ListNode* getNthFromEnd(ListNode* head, int n) {
if (!head) return head;
ListNode* slow = head;
ListNode* fast = head;
while (n-- && fast) {
fast = fast->next;
}
if (n > 0) return nullptr; // 没有n个节点
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
求两个链表的交点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return nullptr;
ListNode* l1 = headA;
ListNode* l2 = headB;
bool flag1 = false, flag2 = false;
while (l1 != l2) {
if (l1 == nullptr) {
if (flag1) return nullptr; // 第二次碰到链表结尾，说明两个链表无交点
flag1 = true;
l1 = headB;
} else {
l1 = l1->next;
}
if (l2 == nullptr) {
if (flag2) return nullptr; // 第二次碰到链表结尾，说明两个链表无交点
flag2 = true;
l2 = headA;
} else {
l2 = l2->next;
}
}
return l1;
}
链表表示的两数相加（lc445）
- 思路：用两个栈分别装两个链表各个节点的值，然后分别出栈做大数相加
回文链表（lc234）
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
// 找到中点并断开（前半段长度<=后半段）
ListNode* slow = head;
ListNode* fast = head->next->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* head2 = slow->next;
slow->next = nullptr;
// 反转后半段
ListNode* dummyHead = new ListNode(-1);
dummyHead->next = head2;
ListNode* cur = head2->next;
while (cur) {
ListNode* nextNode = cur->next;
cur->next = dummyHead->next;
dummyHead->next = cur;
cur = nextNode;
}
head2 = dummyHead->next;
// 比较前半段和后半段
while (head && head2) {
if (head->val != head2->val) return false;
head = head->next;
head2 = head2->next;
}
return true;
}
旋转链表（lc61）
class Solution {
public:
int getLength(ListNode* head) {
int res = 0;
while (head) {
++res;
head = head->next;
}
return res;
}
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
ListNode *fast = head, *slow = head, *prevSlow = head, *prevFast = head;
int len = getLength(head);
k = k % len;
while (k--) {
fast = fast->next;
//if (!fast) fast = head;
}
if (fast == head) return head;
while (fast) {
prevSlow = slow;
slow = slow->next;
prevFast = fast;
fast = fast->next;
}
prevSlow->next = nullptr;
prevFast->next = head;
return slow;
}
};
- 法二：先遍历整个链表获得链表长度n，然后此时把链表头和尾链接起来，在往后走n - k % n个节点就到达新链表的头结点前一个点，这时断开链表即可
