Day4 | Part2
约 185 个字 45 行代码 预计阅读时间 1 分钟
两两交换其中相邻的节点，并返回交换后链表的头节点
如图所示:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy, * curr = head;
while(curr && curr->next) {
prev->next = curr->next; // step1
curr->next = prev->next->next; // step2
prev->next->next = curr; // step3
prev = curr;
curr = curr->next;
}
head = dummy->next;
delete dummy;
return head;
}
|
双指针，fast先移动n步，然后fast和low同时走，fast到结尾，删除slow指向即可
| ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast = head, *slow = head;
for (int i = 0; i < n; i ++) fast = fast->next;
if(!fast) return head->next;
while(fast->next) fast = fast->next, slow = slow->next;
slow->next = slow->next->next;
return head;
}
|
很巧妙的方法，一个从A走，一个从B走，谁先走到空，再绕到另一个开头走
- 定会相交的起始节点碰面（即\(a + c + b = b + c + a\)）
| ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*p = headA, *q = headB;
while(p != q) {
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}
|
Q: 如何判断有环？ 判断出了如何找环的入口?
- 快慢指针: 快的每次走两个，慢的走一个，若相遇则存在环
- 找入口 → 动图参考, 太妙了!!
1
2
3
4
5
6
7
8
9
10
11
12 | ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, *slow = head;
while(fast && fast->next) {
slow = slow->next, fast = fast->next->next;
if (slow == fast) {
ListNode* idx1 = fast, *idx2 = head;
while(idx1 != idx2) idx1 = idx1->next, idx2 = idx2->next;
return idx1;
}
}
return nullptr;
}
|
