Linked List

发表于： 分类于：
字数： 827 阅读：≈ 2分钟

灵神题单

反转链表 

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

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    #因为答案的头节点可能会改，所以搞一个dummy
    dummy=ListNode(next=head)
    pre=dummy
    #移动pre, cur到1和2
    for _ in range(left-1):
        pre=pre.next
    cur=pre.next
    #记录一下此时pre
    p0=pre
    #开始反转2到4这一段, 其实就是分别把2到4的next改了
    for _ in range(right-left+1):
        nxt=cur.next
        cur.next=pre
        pre=cur
        cur=nxt
    #新的pre,cur分别是4，5
    #连接 2 和 5
    p0.next.next=cur
    #连接1和4
    p0.next=pre
    return dummy.next

反转链表关注 pre和cur在开始前和结束后的位置，在这一题中，旧pre的next为新的pre，旧cur的 next为新的cur. Alt text

如果是反转一整条链表，那么最后返回pre就好了。

  1. K 个一组翻转链表

快慢指针

可以用来找中间节点、判断链表是否有环

这种写法，比如有4个节点，slow最后停在第三个节点。

如果把fast初始化为 head.next，slow 最后停在第二个节点。

1
2
3
4
5
6
7
8
9

slow=head
fast=head
while fast and fast.next:
    fast=fast.next.next
    slow=slow.next
    if fast is slow:
        #代表有环
#出循环。代表没有环。
#此时slow为奇数链表的中间节点，偶数链表的第二个中间节点

若初始化fast=head.next,则最后可以得到 slow为正中间的节点。比如节点总数为8，slow停留在第四个节点。

LC 143(快慢指针+反转链表)

143 首先找到中间节点mid，给mid后面都反转。因为从结果来看，这些指针都是需要被反转的。 图上表示反转后的结果，之后只需要不断地让head1.next=head2, head2.next=head1 即可。 经过观察发现，不过是奇数还是偶数链表，当head2.next为 None 时可以结束循环。

复制随机链表

TODO

LC 146. LRU Cache

双向链表->实现插入和删除节点都为 O(1)
dict->key 为 key，value 为 Node
辅助函数: remove(node), get_node(key)->node（返回节点并且把该节点放到链表最前端）, push_front(node)

可以一直保持 dummy.pre为最后一个节点，因为在 push_front的时候就修改了 dummy.pre

LC 106. 相交链表

Alt text 设 A 链表自己的部分长为 x, B 链表自己的部分长为 y, 两个链表共同部分长为 z。
思路：让从 AB 链表出发的两个指针都走上距离x+y+z，它们会在c1节点相遇。