Leetcode【61、82、83、142、143、1171】
Leetcode【61、82、83、142、143、1171】
问题描述：【Linked List】61. Rotate List
解题思路：
这道题是给一个链表，旋转链表，将链表每个结点向右移动 k 个位置。
1、先计算链表长度 size，k = k % size，如果 k % size == 0，则不用移动，直接返回 head；
2、否则，需要将前 size - k 个结点移动到后面。因此只需要循环 size - k 次，找到新链表头部，然后进行指针的交换。最后返回新链表头即可。
注意：这道题虽然是旋转链表，但是实际上并没有真正的进行结点的移动，只是进行了指针的交换。
时间复杂度为 O(n)，空间复杂度为 O(1)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return head
cur, size = head, 1
while cur.next: # cur 结束后记录链表尾
size += 1
cur = cur.next
k = k % size
if k == 0: # 不用旋转
return head
i, pre, newhead = 0, None, head # pre:newhead的前一个, newhead:新头部
while i < size - k:
i += 1
pre = newhead
newhead = newhead.next
cur.next = head
pre.next = None
return newhead问题描述：【Linked List】82. Remove Duplicates from Sorted List II
解题思路：
这道题是给一个链表，去除链表中重复的元素，只留下原链表出现过一次的数字。如 1->2->2->3 变成 1->3。
这道题和下面的 Leetcode 82 思路相同，只不过这道题不需要留下重复的元素。因此除了 Leetcode 82 中的 cur 和 last 外，还需要一个 pre 指向 cur 的前一个位置，便于把所有相同的 cur 全部删除。 同时，要使用一个标记变量 flag 来记录连续一段有没有重复的元素（flag = True），如果没有重复，只是修改 pre 和 cur 向后各移动一位；否则还要进行指针的交换。注意：比如 1,2,2,2,2 这种，循环结束了，但是最后 flag 为 True，因此还需要再进行一次判断，如果 flag 为 True，要进行一次指针的交换操作。
时间复杂度为 O(n)，空间复杂度为 O(1)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
node = ListNode(-1)
node.next = head
head = node
if not head.next:
return head.next
# cur: 指向第一个重复的元素，last: 工作指针，pre: 是 cur 的前一个位置
pre, cur, last = head, head.next, head.next.next
flag = False
while last:
if cur.val == last.val:
flag = True
cur.next = last.next
elif flag: # 有重复
pre.next = last
cur = last
flag = False # 不要忘了修改 flag 为 False，标记下一段是否可能有重复
elif not flag: # 没有重复
pre = cur
cur = last
last = last.next
if flag: # [1,1]或者[1,2,2]
pre.next = last
return head.next问题描述：【Linked List】83. Remove Duplicates from Sorted List
解题思路：
这道题是给一个链表，去除链表中重复的元素。如 1->2->2->3 变成 1->2->3。
只需要两个指针 cur 和 last，cur 指向相同元素的第一个结点，last 为工作指针，每次向后移动。剩下的就是指针的交换和移动。时间复杂度为 O(n)，空间复杂度为 O(1)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
cur, last = head, head.next
while last:
if cur.val == last.val:
cur.next = last.next
else:
cur = cur.next
last = last.next
return head问题描述：【Two Pointers】142. Linked List Cycle II
解题思路：
这道题是给一个链表，判断是否有环。如果有环，找到环的起始位置。
这道题和 Leetcode 【Two Pointers】141. Linked List Cycle 思路一致，都是先使用快慢指针（一个走一步，一个走两步）判断是否有环。
对于这道题，如果有环，还要寻找环的起始位置。思路是：定义一个指针 begin 指向链表头，然后和快慢指针的相遇点 slow（或者 fast），每一次都各走一步，直到二者相遇。证明就不写了，可以参考：LeetCode-142. Linked List Cycle II（详细证明）与龟兔赛跑算法 的证明过程。
时间复杂度为 O(n)，空间复杂度为 O(1)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
flag = True # 标记是否有环
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # 有环
flag = False
break
if flag: # 无环
return None
begin = head
while begin != slow:
begin = begin.next
slow = slow.next
return begin # return slow问题描述：【Linked List】143. Reorder List
解题思路：
这道题是给一个链表，按照 L0→Ln→L1→Ln-1→L2→Ln-2→… 重新排序。
首先第一种想法：遍历一次链表，将各个结点保存到 list 中，按题目顺序重新构造链表即可。更进一步，我们只需要保存后一半链表元素到 list 中，然后将 list 中的元素插入到前半段链表中。但是，这样的操作时间复杂度和空间复杂度均为 O(n)。
有没有时间复杂度为 O(n)、空间复杂度为 O(1) 的做法？因为后半段需要反过来插入，因此我们可以对后半段链表进行反转，然后再按顺序插入到前半段链表就行。链表反转可以参考 Leetcode 【Linked List】206. Reverse Linked List。
实际上，当我们遇到需要从尾部操作的链表问题（如这道题和 Leetcode 【Linked List】445. Add Two Numbers II），都可以先将链表反转，然后再操作，这样就不用使用额外空间了。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return head
l1 = slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
l2 = self.reverse(slow.next) # 后半段反转
slow.next = None # 断开前半段
cur1, cur2 = l1, l2
while cur1 and cur2: # 将后半段依次插入前半段
l2 = l2.next # 插入
cur2.next = cur1.next
cur1.next = cur2
cur1 = cur2.next # 移动
cur2 = l2
return l1
def reverse(self, head):
if not head or not head.next:
return head
pre, cur = head, head.next
while cur:
pre.next = cur.next # 交换
cur.next = head
head = cur
if pre != None:
cur = pre.next # 移动
return head问题描述：【Hash Table】1171. Remove Zero Sum Consecutive Nodes from Linked List
解题思路：
这道题是给一个链表，反复删去链表中总和为 0 的连续结点组成的序列，直到不存在这样的序列为止。
很明显这是一道前缀和问题。之前做过前缀和的一个专题：Leetcode【523、525、560、974】，因此需要用到 Hash Table 存储未出现的前缀和与对应位置的链表结点地址。如果再出现相同前缀和，则就删除两前缀和地址之间的元素即可（修改指针指向）。
注意：
1、要把 {0: None} 加入到 Hash Table 中，作为前缀和的出口（如 1,2,-3 这种情况）。
2、对于链表 1,3,2,-3,-2,5,5,-5,1，从左到右遍历，刚开始得到的前缀和分别为 {0: add(None), 1: add(1), 4: add(3), 6: add(2), 3: add(-3)}，当计算到 -2 位置时，前缀和为 3 + (-1) = 1，前缀和 1 之前在 Hash Table 中出现过，因此需要将 add(1) 的下一个地址指向 -2 的下一个地址 add(5)。但是要注意，这时候还要标记 add(1) 后面的前缀和不可用（因为已经被删除了）。因此，这个时候可以再使用一个集合 discard，用来记录删除的那些地址（从 add(1) 的下一个位置开始循环，一直到 add(-2)）。因此，不仅前缀和要在之前出现过，而且前缀和地址不是 discard 中删除的地址，才可以进行删除。如果不这样做，当碰到 add(5) 时，前缀和为 6，又要删除，从而造成错误的结果。
时间复杂度为 O(n^2)，空间复杂度为 O(n)。
Python3 实现：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
node = ListNode(-1)
node.next = head
head = node
dic = {0: head} # 前缀和:地址
discard = set() # 删除的地址
presum = 0
cur = head.next
while cur:
presum += cur.val
if presum in dic and dic[presum] not in discard:
p = dic[presum].next # 删除的地址保存在集合中
while p != cur:
discard.add(p)
p = p.next
dic[presum].next = cur.next # 指针移动
else:
dic[presum] = cur
cur = cur.next
return head.next