LeetCodeCampsDay4

大多修改/删除/添加操作需要使用dummy_head；仅查询的话，可以不用dummy_head

如果需要一遍扫描完成一些题目，需要借用额外的变量（时间换空间），比如多指针/快慢指针

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

https://leetcode.cn/problems/swap-nodes-in-pairs/

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

示例 1：

img

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

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

思路

初始化

  1. 需要创建dummy_head，方便解题，尤其头节点和第二个节点的交换，有dummy_head后更方便
  2. 如果current is None或current.next is None直接返回；说明链表为空或仅一个节点
  3. 需要一个pre节点，一个current节点
  4. 比如：[[],[1],[2],[3]]
    1. 令[]为dummy_head，且初始化为pre
    2. 令[1]为current节点
    3. 令[2]为tmp节点
    4. 令[3]为nextToGO节点（因为至少有两个节点，所以这里的[3]可能是None，不过没关系）

循环体内

  1. 初始化：tmp节点，指向current.next; 以及nextToGO节点，指向tmp.next
[]-> 1-> 2-> 3-> 4-> None
pre cur tmp nextToGO
  1. 开始swap： #和交换数字的思路比较像
    1. pre.next = tmp
    2. current.next = nextToGO
    3. tmp.next = current

此时的链表
[]-> 2-> 1-> 3-> 4-> None
pre tmp cur nextToGO
  1. 更新pre和current
    1. pre = current
    2. current = nextToGO

代码

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def __printVal(self, node):
        print(f"node.val {node.val}")

    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(next = head)

        pre = dummy_head
        current = dummy_head.next

        # init
        if current is None or current.next is None:
            return head
        
        while current and current.next:
            temp = current.next
            nextToGo = temp.next

            # swap
            pre.next = temp
            current.next = nextToGo
            temp.next = current
            
            # update
            pre = current
            current = nextToGo
        
        return dummy_head.next

如果不使用nextToGo也可以，但需要理解好几个节点的关系

初始化

  1. 需要创建dummy_head，方便解题，尤其头节点和第二个节点的交换，有dummy_head后更方便
  2. 如果current is None或current.next is None直接返回；说明链表为空或仅一个节点
  3. 需要一个pre节点，一个current节点
  4. 比如：[[],[1],[2],[3]]
    1. 令[]为dummy_head，且初始化为pre
    2. 令[1]为current节点
    3. 令[2]为tmp节点

循环体内

  1. 初始化：tmp节点，指向current.next
[]-> 1-> 2-> 3-> 4-> None
pre cur tmp
  1. 开始swap： #和交换数字的思路比较像
    1. pre.next = tmp
    2. current.next = tmp.next
    3. tmp.next = current

此时的链表
[]-> 2-> 1-> 3-> 4-> None
pre tmp cur
  1. 更新pre和current
    1. pre = current
    2. current = current.next
1
2
3
4
5
6
7
8
9
#
            temp = current.next
            # swap
            pre.next = temp
            current.next = temp.next
            temp.next = current
            # update
            pre = current
            current = current.next

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

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

示例 1：

img

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

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

提示：Maintain two pointers and update one with a delay of n steps.

思路

  1. 使用dummy_head，方便解题
  2. 使用快慢指针，快指针比慢指针多走n+1步，因为需要让慢指针stops at 被删除节点的前一个节点;从而一次扫描即可实现

代码

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
      	# init a dummy head
        dummy_head = ListNode(next = head)
        current = dummy_head
        slow = dummy_head
				# Move the current pointer forward by n+1 steps so that the slow pointer stops at the node immediately before the one that need to be deleted.
        while n+1 and current:
            n -= 1
            current = current.next
        # 
        while current:
            current = current.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next
      
      
      	# The following method is my dummy one.
        # count = 0
        # while current.next:
        #     current = current.next
        #     if count< n:
        #         count += 1
        #         continue
        #     else:
        #         slow = slow.next
            
        # slow.next = slow.next.next
        # return dummy_head.next

面试题 02.07. 链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

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

图示两个链表在节点 c1 开始相交**：**

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

img

1
2
3
4
5
输入：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 个节点。

示例 2：

img

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

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

**进阶：**你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

思路

  1. 可以使用dummy_head，确实方便一点儿; 不过本题目没有插入/删除，可以不用dummy_head.
  2. 注意它是“指针相等”而不是数值相等；并且A和B如果相交，它们则一定是到某个节点后，是指向同一节点的，不要把它们当成两条完全独立的链表处理；
  3. 可以通过判断最后一个元素是否相等来初步筛选
  4. 如果两个链表长度相等，则可以同步地遍历，找到共同节点
  5. 如果两个链表长度不相等，可以让长的先遍历n步n = abs(L_A - L_B), where L_A is the length of A. 然后再按长度相等的方式处理

代码

  • 时间复杂度：O(L_A + L_B) [指A和B的总长度]
  • 空间复杂度：O(1)
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 如果A,B链表长度相同，则可以同步遍历
        # 如果A,B链表长度不同，则让长的先走n步, where n = abs(L_a - L_b)
        L_A = 0
        L_B = 0
        # dh指dummy_head
        dhA = ListNode(next = headA)
        endA = dhA
        while endA.next:
            endA = endA.next
            L_A += 1
        dhB = ListNode(next = headB)
        endB = dhB
        while endB.next:
            endB = endB.next
            L_B += 1
        # If the last elements are not equal return NULL
        if endA != endB or L_A == 0 or L_B == 0:
            return 

        curA = dhA
        curB = dhB
        
        # Adjust the Make sure they start at same step.
        gap = abs(L_B - L_A)
        if L_A < L_B:
            for _ in range(gap):
                curB = curB.next
        elif L_A > L_B:
            for _ in range(gap):
                curA = curA.next
				
        while curA.next:
            curA = curA.next
            curB = curB.next
            if curA == curB:
                return curA
        return

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

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

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

不允许修改 链表。

示例 1：

img

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

示例 2：

img

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

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

快慢指针思路

  1. 这题不用dummy_head
  2. 本题有两个任务：
    1. 是否有环
    2. 如果有环，怎么找到环的入口

是否有环

如果使用快慢指针的方式，快指针每次走两步，慢指针每次走一步，如果有环，一定能相遇

img

如何找环的入口

  • 令头节点到入口节点的距离为x(个节点)。
  • 环形入口节点 到 fast指针与slow指针相遇节点 节点数为y。
  • 从相遇节点 再到环形入口节点节点数为 z。

如图所示：

img

那么相遇时：

  • slow指针走过的节点数为: x + y
  • fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2 ：

(x+y)∗2=x+y+n(y+z)(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，则需要求的元素是x，因为x表示：the distance between 头节点 and 入口节点。即x = n (y + z) - y

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次都只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2（也可以让slow继续走，并且让fast每次只走一步）

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

img

那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。

其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

代码

  • 时间复杂度 O(N) --slow走完一遍即可（slow不用在环内转圈）/60ms
  • 空间复杂度 O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 快慢指针，如果有环，快指针必能遇到慢指针
        fast = head
        slow = head
				# 注意退出条件，只控制fast即可了
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            # 如果快慢指针相遇，说明有环，当前位置是相遇点；下一任务是找入口
            if slow == fast:
                # 让slow从头开始，而fast仍在相遇点；fast和slow都是每次走一步
                slow = head
                while slow != fast:
                    fast = fast.next
                    slow = slow.next
                return slow
        return

普通思路

创建一个visited_list，将遍历过的节点都添加进去，如果新的节点已经存在于visited_list说明它就是“入口节点”

代码

  • 时间复杂度 O(N)—844ms
  • 空间复杂度 O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
				# 普通解法，记录所有节点
        visitedList = []
        cur = head
        while cur:
            if cur in visitedList:
                return cur
            visitedList.append(cur)
            cur = cur.next
        return