Chapter 2: Linked List

知识解析

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

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

2.1 Singly Linked List 的基本操作规范

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

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 头的操作

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 寻找特定节点的问题

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的问题

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处理,因为靠前计算结果依赖于后面的计算结果)

Last updated

Was this helpful?