Chapter 2: Linked List

知识解析

除特别注明外，本文都使用以下所示的singly linked list。

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

2.1 Singly Linked List 的基本操作规范

Linked List的问题，核心在于操作 + 移动。 先考虑一轮操作，需要哪些变量，比如 prev, next 对应操作 arr.push ，对linked list有 tail.next = curr tail = tail.next 对应移动 idx += 1 ，对linked list有 [current node] = [current node].next ，如果有 prev 变量则有 prev = prev.next ，如果有 next_node 变量则有 next_node = next_node.next

在修改linked list时，注意“先连后断”的原则。先更改原先 next 为 null 的节点，更新其next之后，就可以更改本来指向其next的节点，以此类推，最后处理的节点是需要删除next而不是更改next的

2.1.1 注意corner case ( curr == head, curr == tail , 或 curr == None 。凡是修改list但不改变每个node的value的操作，只需要考虑：谁的next 指针受到影响，那么就需要维护这些节点。

def delNode(prev: ListNode) -> None :
    prev.next = prev.next.next

链表不能向后访问，所以记录prev变量比记录curr 更普适，因为前者可以推出后者，而反之则不然。当前节点可以用prev.next 来表示，这样就不用维护两个变量。

2.1.2 遍历Linked list时，每次循环内只对一个或一对节点进行题意中的操作。（不要试图对下一个或者下一对进行操作）

e.g. Reverse the linked list and return the new head. (LeetCode: Reverse Linked List )

def reverseList(self, head: ListNode) -> ListNode:
    # Of course, it can also be done with recursion/stack
    prev, curr = None, head
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    return prev 

2.1.3 处理两个长度未必相等的linked list的问题，循环的条件一般用 while node1 and node2 , 再处理剩下非空的那个list。

e.g Merge two sorted linked lists and return it as a new list.(Leetcode: Merge Two Sorted Lists)

2.2 涉及到对Linked List 头的操作

对于涉及到Linked List头节点的操作，不妨用dummy = ListNode(0) dummy.next = head来避开处理head发生变化的情况，最后用dummy.next 作为头节点即可。

e.g. Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. ( LeetCode: Partition List )

2.3 寻找特定节点的问题

对于寻找list某个特定位置的问题，不妨用 runner technique：chaser, runner = head, head; chaser与runner以不同速率或不同起点前进，直到runner满足一定条件时，结果由这两个共同决定。

e.g.1 Find the middle point of the linked list

def middlePoint(head: ListNode) -> ListNode:
    chaser, runner = head, head
    while runner.next and runner.next.next:
        chaser = chaser.next
        runner = runner.next.next
    return chaser

e.g.2 Find the kth to last element of a singly linked list. e.g.3 Given a circular linked list, return the node at the beginning of the loop. (LeetCode: Linked List Cycle ii) e.g.4 Given a list, rotate the list to the right by k places, where k is non-negative. (Leetcode: Rotate List 先查找，再拆分)

模式识别

2.4 交换node的问题

交换两个node，有且仅有这两个node以及他们prev node的next指针会受到影响，那么根据2.1.1，需要a. 先交换两个prev node的next ； b. 再交换这两个node的next。无论这两个node的相对位置还是绝对位置，以上的处理总是正确的。

e.g. Given a linked list, swap every two adjacent nodes and return its head.( Leetcode: Swap Nodes in Pairs ) Given 1->2->3->4, you should return the list as 2->1->4->3.

def swapPairs(self, head: ListNode) -> Optional[ListNode]:   
    dummy = ListNode(0)
    dummy.next = head
    
    prev, first = dummy, head
    while first and first.next:
        second = first.next
        prev.next, first.next = first.next, prev.next   # swap prev nodes' next
        first.next, second.next = second.next, first.next   # swap two nodes' next
        prev = first
        first = first.next

    return dummy.next

2.5 倒序访问问题

如果对靠前节点的处理必须在靠后节点之后，即倒序访问问题，则可视为recursion问题，或可以用stack等效解决。

e.g. 1 Given input ( 7->1->6 ) + ( 5->9->2 ), output 2->1->9. ( LeetCode: add Two Numbers 无需递归顺序访问即可，因为靠前计算结果不依赖于靠后节点） e.g.2 Given input ( 6->1->7 ) + ( 2->9->5 ), output 9->1->2. ( LeetCode: add Two numbers II 用递归或stack处理，因为靠前计算结果依赖于后面的计算结果)