代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例

输入：head = [1,2,3,4]
输出：[2,1,4,3]

思路

1. 交换节点的值，而非交换节点指针
2. 涉及两个指针，我们用cur和cur.next表示，每次走两步
3. while循环条件：cur and cur.next非空

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/swap-nodes-in-pairs/
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
    交换节点val，并不是交换节点
    """

    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            temp_node = cur.next
            temp_val = temp_node.val
            temp_node.val = cur.val
            cur.val = temp_val
            cur = temp_node.next
        return head


if __name__ == '__main__':
    pass

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

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

、

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路

1. 本题采用快慢指针（slow和fast指针）方法进行解题
2. 题目中给出了n的有效性，因此不需要判断；当链表长度为1时，n=1时，此时删除头节点，比较费劲，因此采用虚拟头节点方法
3. slow和fast指针同时指向dummy_head节点，先让fast走n+1步，然后同时移动slow和fast指针，直到fast指针为None，此时进行节点删除操作

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
    本题采用快慢指针方法进行解题，题目中给出了n的有效性，因此不需要判断；当链表长度为1时，n=1时，此时删除头节点，比较费劲，
    因此采用虚拟头节点方法：
    slow和fast指针同时指向dummy_head节点，先让fast走n+1步，然后同时移动slow和fast指针，直到fast指针为None，
    此时进行节点删除操作
    """

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode()
        dummy_head.next = head
        slow = dummy_head
        fast = dummy_head
        for i in range(n + 1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy_head.next


if __name__ == '__main__':
    pass

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

02.07.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路

1. 快慢指针，比较节点相等，而非节点数值
2. 先计算出两个链表的长度，使用快慢指针，根据长度差，分别指向长度长的head和长度短的head，先让快指针移动长度差次，然后快慢指针同时移动，比较两个节点，相等则直接返回，遍历到最后不相等，则返回None

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    """
    先计算出两个链表的长度，使用快慢指针，根据长度差，分别指向长度长的head和长度短的head，
    先让快指针移动长度差次，然后快慢指针同时移动，比较两个节点，相等则直接返回，遍历到最后
    不相等，则返回None
    """

    def getListLength(self, head: ListNode) -> int:
        cur = head
        length = 0
        while cur:
            length += 1
            cur = cur.next
        return length

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        length_a = self.getListLength(headA)
        length_b = self.getListLength(headB)
        diff = abs(length_b - length_a)
        long_cur = headA
        short_cur = headB
        if length_b > length_a:
            long_cur = headB
            short_cur = headA
        while diff:
            long_cur = long_cur.next
            diff -= 1
        while long_cur:
            if long_cur == short_cur:
                return long_cur
            long_cur = long_cur.next
            short_cur = short_cur.next
        return None


if __name__ == '__main__':
    pass

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
42
43
44
45
46
47
48
49
50

142.环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路

1. 快慢指针，fast和slow指针同时指向head节点，fast指针每次走2步，slow指针每次走1步；
2. 当fast和slow指针在环中相遇时，将cur指针指向head，cur和slow指针每次走1步，当两个指针相遇时，即为换环的入口。不知道为啥，提交代码，需要把ListNode的定义去掉…

代码

#  !/usr/bin/env  python
#  -*- coding:utf-8 -*-
# @Time   :  2022.10
# @Author :  hello algorithm!
# @Note   :  https://leetcode.cn/problems/linked-list-cycle-ii/
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
    fast和slow指针同时指向head节点，fast指针每次走2步，slow指针每次走1步，当fast和slow指针在环中
    相遇时，将cur指针指向head，cur和slow指针每次走1步，当两个指针相遇时，即为换环的入口
    不知道为啥，提交代码，需要把ListNode的定义去掉......
    """

    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                cur = head
                while cur != slow:
                    cur = cur.next
                    slow = slow.next
                return cur
        return None


if __name__ == '__main__':
    head = ListNode(3)
    l2 = ListNode(2)
    l3 = ListNode(0)
    l4 = ListNode(-4)
    head.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l2
    s = Solution()
    s.detectCycle(head)

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
42
43
44
45
46
47
48

总结

1. 双指针或者快慢指针，虚拟头节点和while循环终止条件，需要手动模拟确认
2. 先考虑一般情况，在考虑边界