算法刷题Day4 两两交换链表中的节点+删除链表的倒数第N个结点+链表相交+环形链表

day 4 链表

24. 两两交换链表中的节点

使用dummy节点可以极大地简化过程

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(-1, head);
        ListNode *cur = &dummy;

        while (cur && cur->next && cur->next->next)
        {
            ListNode *first = cur->next;
            ListNode *second = cur->next->next;
			// 交换两个节点的位置
            first->next = second->next;
            second->next = first;
            cur->next = second;
            // 向后移动两个节点
            cur = cur->next->next;
        }

        return dummy.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

19. 删除链表的倒数第 N 个结点

有个地方折磨了我有一会儿，是粗心导致的，而且提示的错误也很难发现是哪里导致的。就是在case为head = [1], n = 1时，最后释放了tmp之后（此时tmp刚好指向head，我还return head;，意思就是操作了已经被我释放的内存，leetcode就报错了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(-1, head);
        ListNode *fast = &dummy;

        while (fast->next && n--)
        {
            fast = fast->next;
        }

        ListNode *slow = &dummy;
        while (fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }

        ListNode *tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;

        return dummy.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

面试题 02.07. 链表相交

老生常谈的题目了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA, *curB = headB;

        while (curA != curB)
        {
            curA = curA ? curA->next : headB;
            curB = curB ? curB->next : headA;
        }

        return curA;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

142. 环形链表II

还是用快慢指针，如果能够相遇，证明存在环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) // 如果不存在环,fast会先链表末尾nullptr,会跳出循环
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true; // 应该要返回相交的那个节点才对
        }

        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

返回相交的那个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        bool flag = false;

        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) 
            {
                flag = true;
                break;
            }
        }

        if (flag) // 存在环
        {
            ListNode *cur = head;
            while (cur != fast)
            {
                cur = cur->next;
                fast = fast->next;
            }
            return cur;
        }
        else // 不存在环
        {
            return nullptr;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

个人理解

如果存在环的话，slow指针走一步，fast指针走两步，两个指针总能相遇。因为fast指针走的快，在存在环的情况下，fast总能”追“上slow。因此，可以用这个方法判断有没有环存在。

在确定有环存在之后，顺便能得到slow指针和fast指针相遇的位置。因为fast的步数是slow的两倍，记从head到slow的步数为a，那么fast走过的步数为2a，在这个链表中，走过a步和走过2a步最终能到达同一个节点。为了求环的入口点，我们可以设置两个指针，一个从起始位置head开始，一个从a位置开始，一同出发，最终一定能在2a位置相遇，由于2a处于环内，那么在2a之前它们实际上已经重合，再往前推，它们在环的入口点就已经重合。所以它们第一次相遇的点，就是环的入口点！

以上都是我自己理解的方法，数学证明的话可以看随想录的笔记。