链表专题
61 旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
143 重排链表
142
假设入口为 $A$， 到入口的距离为 $x$， 快慢指针相遇点为 $B$， $A$ 到 $B$ 的距离为 $y$， $B$ 到 $A$ 的距离为 $z$。
那么当快慢指针相遇时， 两指针走过的距离为：
\[l_1 = x + y + k_1(y + z)\] \[l_2 = x + y + k_2(y + z)\]又:
\[x + y + k_2(y + z) = 2(x + y + k_1(y + z))\]有：
\[x + y = (k_2 - 2k_1)(y + z) \Rightarrow x = (k_1 - 2k_1 -1)(y + z) + z\]也就是说 $x$ 的长度为环的周长的整数倍加上 BA 的长度。 如果两个指针分别从头和从 B 点开始走， 那么一个指针到达 A 点时， 另一个指针也必然到达。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head: return None
slow = fast = head
while fast:
slow = slow.next
fast = fast.next
if fast: fast = fast.next
else: break
if slow == fast:
fast = head
while(fast != slow):
fast = fast.next
slow = slow.next
return fast
return None
206 反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
"""
- c = b->next
- b ->next = a
- a = b, b = c
"""
def reverseList(self, head: ListNode) -> ListNode:
if not head: return None
a = head
b = head.next
while b:
c = b.next
b.next = a
a = b
b = c
head.next = None
return a
-
Previous
【深度学习】In Defense of Scene Graphs for Image Captioning -
Next
【深度学习】On the Role of Scene Graphs in Image Captioning
