Reverse Linked List

 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]:
    #Answer head might change, so use dummy
    dummy=ListNode(next=head)
    pre=dummy
    #Move pre, cur to positions 1 and 2
    for _ in range(left-1):
        pre=pre.next
    cur=pre.next
    #Record current pre
    p0=pre
    #Reverse from 2 to 4, essentially changing next pointers
    for _ in range(right-left+1):
        nxt=cur.next
        cur.next=pre
        pre=cur
        cur=nxt
    #New pre,cur are 4,5
    #Connect 2 and 5
    p0.next.next=cur
    #Connect 1 and 4
    p0.next=pre
    return dummy.next

Reverse linked list focuses on pre and cur positions before start and after end. In this case, old pre.next becomes new pre, old cur.next becomes new cur.

If reversing entire list, return pre at end.

25. Reverse Nodes in k-Group

Fast-Slow Pointers

Find middle node, detect cycles.

This approach: with 4 nodes, slow ends at third node.

If initialize fast=head.next, slow ends at second node.

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:
        #cycle detected
#Exit loop: no cycle
#slow is middle node for odd list, second middle for even list

If initialize fast=head.next, slow gets exact middle node. For 8 nodes, slow at fourth node.

LC 143 (Fast-Slow Pointers + Reverse List)

Find middle node mid, reverse everything after mid. From result, these pointers need reversal. Diagram shows reversed result. Then repeatedly set head1.next=head2, head2.next=head1. Observation: whether odd or even list, loop can end when head2.next is None.

Copy Random Linked List

TODO

LC 146. LRU Cache

Doubly linked list → O(1) insert and delete nodes dict → key as key, value as Node

Helper functions: remove(node), get_node(key)→node (return node and move to front: remove then push_front), push_front(node)

Can maintain dummy.pre as last node since push_front modifies dummy.pre

LC 106. Intersection of Two Linked Lists

Let A list own part length x, B list own part length y, common part length z. Idea: pointers from A and B both travel distance x+y+z, they meet at node c1.