LeetCode算法题整理（链表篇）LinkedList

Posted on   |   Updated on | In | | Visitors

链表的定义

1
2
3
4
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

2. Add Two Numbers

两个链表相加

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addTwoNumbers(l1, l2):
    l = head = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1+v2+carry, 10)
        l.next = ListNode(val)
        l = l.next
    return head.next

445. Add Two Numbers II

跟上题类似，只不过是进位方式不同。原题

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

方法一：先reverse再相加，最后再reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    
    def reverse(head):
        prev = None
        while head:
            head.next, prev, head = prev, head, head.next
        return prev
    
    ans = head = ListNode(0)
    l1, l2 = reverse(l1), reverse(l2)
    carry = 0
    while l1 or l2 or carry:
        v1 = v2 = 0
        if l1:
            v1 = l1.val
            l1 = l1.next
        if l2:
            v2 = l2.val
            l2 = l2.next
        carry, val = divmod(v1+v2+carry, 10)
        head.next = ListNode(val)
        head = head.next
    return reverse(ans.next)
方法二：由于Python int没有限制，所以可以遍历相加，再从尾到头还原节点。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    v1 = v2 = 0
    while l1:
        v1 = v1*10 + l1.val
        l1 = l1.next
    while l2:
        v2 = v2*10 + l2.val
        l2 = l2.next
    val = v1 + v2
    tail, head = None, None
    while val > 0:
        head = ListNode(val % 10)
        head.next = tail
        tail = head
        val //= 10
    return head if head else ListNode(0)

21. Merge Two Sorted Lists

合并两个有序链表。原题

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

方法1：iteratively 迭代

1
2
3
4
5
6
7
8
9
10
def mergeTwoLists(l1, l2):
    l = head = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            l.next, l1 = l1, l1.next
        else:
            l.next, l2 = l2, l2.next
        l = l.next
    l.next = l1 or l2
    return head.next

方法2：recursively 递归

1
2
3
4
5
6
7
8
9
10
def mergeTwoLists(l1, l2):
    # 判断是否存在None
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

23. Merge k Sorted Lists

合并k个有序列表。原题

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

方法一：Brute Force. time: O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    ans = []
    for l in lists:
        while l:
            ans.append(l.val)
            l = l.next
    h = head = ListNode(0)
    for v in sorted(ans):
        h.next = ListNode(v)
        h = h.next
    return head.next

方法二：优先级队列。本来优先级就没有方法一快，再加上Python3中的比较符机制不同，导致要实现__lt__方法，就更慢了。不过理论时间复杂度是比方法一小的。Time: O(Nlogk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class CmpNode:
    
    def __init__(self, node):
        self.node = node
        
    def __lt__(self, other):
        return self.node.val < other.node.val
    
class Solution:
        
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        from queue import PriorityQueue
        head = h = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put(CmpNode(l))
        while not q.empty():
            to_add = q.get().node
            h.next = to_add
            h = h.next
            if to_add.next:
                q.put(CmpNode(to_add.next))
        return head.next
方法三：规避ListNode的比较，以解决上述问题。只要加上该链表在原数组中的索引位置，就一定不会重复，从而忽略对ListNode的比较。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    from queue import PriorityQueue
    q = PriorityQueue()
    for idx, l in enumerate(lists):
        if l:
            q.put((l.val, idx, l))
    h = head = ListNode(0)
    while not q.empty():
        val, idx, node = q.get()
        h.next = node
        h, node = h.next, node.next
        if node:
            q.put((node.val, idx, node))
    return head.next
方法四：俩俩合并。Time: O(Nlogk) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    
    def merge_two(l1, l2):
        dummy = h = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                h.next = l1
                l1 = l1.next
            else:
                h.next = l2
                l2 = l2.next
            h = h.next
        h.next = l1 or l2
        return dummy.next

    pairs = lists
    while len(pairs) > 1:
        if len(pairs) & 1: pairs.append(None)
        pairs = [merge_two(pairs[i], pairs[~i]) for i in range(len(pairs)//2)]
    return pairs[0] if pairs else None
方法五：和优先队列一样，使用堆实现。个人觉得比优先级队列好写一点。 
1
2
3
4
5
6
7
8
9
10
11
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    dummy = h = ListNode(0)
    heap = []
    for i, l in enumerate(lists):
        if l: heapq.heappush(heap, (l.val, i, l))
    while heap:
        val, i, l = heapq.heappop(heap)
        h.next, l = l, l.next
        if l: heapq.heappush(heap, (l.val, i, l))
        h = h.next
    return dummy.next

141. Linked List Cycle

判断一个链表是否有环。原题

经典的一道题，看成两个人在赛跑，如果有环，快的人会和慢的人相遇

1
2
3
4
5
6
7
def hasCycle(self, head):
    slow = fast = head:
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if fast is slow:
            return True
    return False

142. Linked List Cycle II

求链表中环的入口节点。原题

  • 首先判断此链表是否有环。
  • 然后在相交点和头结点一起走，一定会在入口相遇。
Consider the following linked list, where E is the cylce entry and X, the crossing point of fast and slow.
H: distance from head to cycle entry E
D: distance from E to X
L: cycle length
  ​                _____
  ​               /     \
head_____H______E       \
  ​              \       /
  ​               X_____/   

   If fast and slow both start at head, when fast catches slow, slow has traveled H+D and fast 2(H+D). 
Assume fast has traveled n loops in the cycle, we have:
2H + 2D = H + D + L  -->  H + D = nL  --> H = nL - D
Thus if two pointers start from head and X, respectively, one first reaches E, the other also reaches E. 
In my solution, since fast starts at head.next, we need to move slow one step forward in the beginning of part 2

1
2
3
4
5
6
7
8
9
10
11
12
13
def detectCycle(self, head):        
    fast = slow = head
    # 检测是否有环
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    # 找出入口节点
    while head is not slow:
        head, slow = head.next, slow.next
    return head

206. Reverse Linked List

倒置一个链表。原题

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

方法一： iteratively

1
2
3
4
5
6
7
8
def reverseList(head):
    prev = None
    while head:
        cur = head
        head = head.next
        cur.next = prev
        prev = cur
    return prev

方法二：使用一行赋值

1
2
3
4
5
def reverseList(self, head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev
Python同时给多个变量赋值。

方法三：递归

1
2
3
4
5
6
def reverseList(self, head, prev=None):
    if not head:
      return prev
  
    cur, head.next = head.next, prev
    return self.reverseList(cur, head)

92. Reverse Linked List II

跟上题不同的是，只倒置指定区间的部分。原题

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:

    root = h = ListNode(0)
    h.next = head
    
    for _ in range(m-1):
        h = h.next
    cur_head = h
    p1 = p2 = cur_head.next
    for _ in range(n-m):
        p2 = p2.next
    prev = p2.next if p2 else None
    if p2:
        p2.next = None
    while p1:
        p1.next, prev, p1 = prev, p1, p1.next
    cur_head.next = prev
    return root.next
方法二：遍历一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:

    dummy = p = ListNode(0)
    dummy.next = head
    for _ in range(m-1): p = p.next
    tail = p.next

    for _ in range(n-m):
        tmp = p.next
        p.next = tail.next
        tail.next = tail.next.next
        p.next.next = tmp

    return dummy.next

### 160. Intersection of Two Linked Lists
#### 两个链表求相交。原题

1
2
3
4
5
6
def getIntersectionNode(self, headA, headB):
    p1, p2 = headA, headB
    while p1 is not p2:
        p1 = p1.next if p1 else headB
        p2 = p2.next if p2 else headA
    return p1


### 138. Copy List with Random Pointer

#### 深拷贝一个复杂链表，链表多包含了一个随机指针。原题

Time-O(2n), Memory-O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
def copyRandomList(self, head):
    cp_map = {}
        
    m = n = head
    while m:
        cp_map[m] = RandomListNode(m.label)
        m = m.next
    while n:
        cp_map[n].next = cp_map.get(n.next)
        cp_map[n].random = cp_map.get(n.random)
        n = n.next
        
    return cp_map.get(head)
 Time-O(n), Memory-O(n). 这种方式是相当于把第一次迭代的过程委托给了defaultdict，通过创建一个默认的对象，再去修改它的label值。

1
2
3
4
5
6
7
8
9
10
11
def copyRandomList(self, head):
    from collections import defaultdict
    cp = defaultdict(lambda: RandomListNode(0))
    cp[None] = None
    n = head
    while n:
        cp[n].label = n.label
        cp[n].next = cp[n.next]
        cp[n].random = cp[n.random]
        n = n.next
    return cp[head]



### 237. Delete Node in a Linked List
#### 在链表中删除节点。给定的节点不是尾节点。原题

1
2
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]

开始看到这题的思路是，要是能拿到父节点就好了，然后这道题需要别的思路，其关键在于复制

1
2
3
def deleteNode(self, node):
    node.val = node.next.val  # 4->1->1->9
    node.next = node.next.next  # 4->1->9


### 203. Remove Linked List Elements
#### 删除链表中值为val的元素。原题
方法一：遍历head并构建新的ListNode。

1
2
3
4
5
6
7
8
def removeElements(self, head, val):
    l = res = ListNode(0)
    while head:
        if head.val != val:
            l.next = ListNode(head.val)
            l = l.next
        head = head.next
    return res.next

方法二：更喜欢这个方法。 
1
2
3
4
5
6
7
8
9
def removeElements(self, head: 'ListNode', val: 'int') -> 'ListNode':
    l = ListNode(0)
    l.next, ans = head, l
    while l and l.next:
        if l.next.val == val:
            l.next = l.next.next
        else:
            l = l.next
    return ans.next

83. Remove Duplicates from Sorted List

删除有序链表中重复的节点。原题

1
2
3
4
5
6
7
8
def delete_duplicates(head):
    root = head
    while head and head.next:
        if head.val == head.next.val:
            head.next = head.next.next
        else:
            head = head.next
    return root

82. Remove Duplicates from Sorted List II

和上题不同的是，重复的节点要全部删除。原题

1
2
Input: 1->2->3->3->4->4->5
Output: 1->2->5

方法一：首次AC的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def deleteDuplicates(self, head: ListNode) -> ListNode:
    prev = ans = ListNode(0)        
    prev.next = h = head
    
    while h and h.next:
        remove = False
        while h.next and h.val == h.next.val:
            h.next = h.next.next
            remove = True
        if remove:
            prev.next = h.next
        else:
            prev = prev.next
        h = h.next
    return ans.next

876. Middle of the Linked List

链表中点，如果偶数个，则返回第二个节点。原题

1
2
3
4
5
6
7
8
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.
1
2
3
4
5
def middleNode(self, head: 'ListNode') -> 'ListNode':
    fast = slow = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

234. Palindrome Linked List

判断一个链表是否是回文链表。原题

1
2
Input: 1->2->2->1
Output: true

方法一：此题为倒置链表和快慢指针的总和应用。

1
2
3
4
5
6
7
8
9
10
11
def isPalindrome(self, head: 'ListNode') -> 'bool':
    rev = None
    slow = fast = head
    while fast and fast.next:
        fast = fast.next.next
        slow.next, rev, slow = rev, slow, slow.next
    if fast:
        slow = slow.next
    while rev and rev.val == slow.val:
        rev, slow = rev.next, slow.next
    return rev is None

方法二：上述方法有一个缺点就是改变了原始的head，这里进行一些改进。

1
2
3
4
5
6
7
8
9
10
11
12
13
def isPalindrome(self, head):
    rev = None
    fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, head = head, rev, head.next
    tail = head.next if fast else head
    isPali = True
    while rev:
        isPali = isPali and rev.val == tail.val
        head, head.next, rev = rev, head, rev.next
        tail = tail.next
    return isPali

24. Swap Nodes in Pairs

成对转换链表。原题

1
Given 1->2->3->4, you should return the list as 2->1->4->3.
1
2
3
4
5
6
7
8
def swapPairs(self, head: ListNode) -> ListNode:
    prev, prev.next = self, head
    while prev.next and prev.next.next:
        a = prev.next    # current
        b = a.next
        prev.next, b.next, a.next = b, a, b.next
        prev = a
    return self.next

方法二：这里有个阴间写法，只创建一个变量。注意复制顺序，不能将p.next放到前面。

1
2
3
4
5
6
def swapPairs(self, head: ListNode) -> ListNode:
    p, p.next = self, head
    while p.next and p.next.next:
        p.next.next.next, p.next.next, p.next = p.next, p.next.next.next, p.next.next
        p = p.next.next
    return self.next

19. Remove Nth Node From End of List

删除倒数第N个节点。原题

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
1
2
3
4
5
6
7
8
9
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    slow = dummy = ListNode(0)
    dummy.next = fast = head
    for _ in range(n):
        fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

328. Odd Even Linked List

重排链表，使奇数位节点在前，偶数位节点在后，就地排序。原题

1
2
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
1
2
3
4
5
6
7
8
9
10
11
12
def oddEvenList(self, head: ListNode) -> ListNode:
    if not head:
        return None
    odd = head
    even_h = even = head.next
    while even and even.next:
        odd.next = odd.next.next
        odd = odd.next
        even.next = even.next.next
        even = even.next
    odd.next = even_h
    return head

***. Sort a linked list that is sorted alternating asc and desc

这题不是LC上的，是面经里的，要求将一个奇数位升序，偶数位降序的链表转成一个升序的链表。

1
2
Input List:   10->40->53->30->67->12->89->NULL
Output List:  10->12->30->40->53->67->89->NULL

方法一：分别参考了328，206，21三题，但是有一个副作用，就是将输入的链表改变了，一开始我是想针对链表就地修改，但是发现最后合并的时候又不太好实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def sort_alternating(head: ListNode) -> ListNode:
    if not head:
        return None
    # separate two lists
    odd = head
    even_h = even = head.next
    while even and even.next:
        odd.next = odd.next.next
        odd = odd.next
        even.next = even.next.next
        even = even.next
    odd.next = None   # for last even tail ！！
    # reverse the one with descending order
    prev = None
    while even_h:
        even_h.next, prev, even_h = prev, even_h, even_h.next

    # merge both lists
    ans = h = ListNode(0)
    while head and prev:
        if head.val <= prev.val:
            h.next, head = head, head.next
        else:
            h.next, prev = prev, prev.next
        h = h.next
    h.next = head or prev
    # head is not head original
    return ans.next

方法二：修改了方法一中的不足，在一开始就建立两个链表。两个链表要分开迭代才不会遗漏元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def sort_alternating(head: ListNode) -> ListNode:
    if not head:
        return None
    # separate two lists
    odd_head = odd_h = ListNode(0)
    even_head = even_h = ListNode(0)
    odd = head
    even = head.next
    while odd:
        odd_h.next = ListNode(odd.val)
        odd, odd_h = odd.next.next if odd.next else None, odd_h.next
    while even:
        even_h.next = ListNode(even.val)
        even, even_h = even.next.next if even.next else None, even_h.next
    
    # reverse the one with descending order
    prev = None
    odd_head, even_head = odd_head.next, even_head.next
    while even_head:
        even_head.next, prev, even_head = prev, even_head, even_head.next

    # merge both lists
    ans = h = ListNode(0)
    while odd_head and prev:
        if odd_head.val <= prev.val:
            h.next, odd_head = odd_head, odd_head.next
        else:
            h.next, prev = prev, prev.next
        h = h.next
    h.next = odd_head or prev
    return ans.next

148. Sort List

给链表排序。原题

1
2
Input: 4->2->1->3
Output: 1->2->3->4

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def sortList(self, head: ListNode) -> ListNode:
    
    def merge_both(l1, l2):
        l = h = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                l.next, l1 = l1, l1.next
            else:
                l.next, l2 = l2, l2.next
            l = l.next
        l.next = l1 or l2
        return h.next
    
    def merge_sort(h):
        if not h or not h.next:
            return h
        slow = fast = h
        prev = None
        while fast and fast.next:
            prev, slow, fast = slow, slow.next, fast.next.next
        prev.next = None
        left = merge_sort(h)
        right = merge_sort(slow)
        return merge_both(left, right)
    
    return merge_sort(head)
方法二：要求是常数空间复杂度实现，看到有人说递归栈也要算在空间内，那就只能写成迭代。迭代确实比较复杂这是评论区中的一个方法。这里是官方题解给的方法，写得很好了。大体思路和我想的差不多，返回尾节点的操作一开始想放到cut_list中而不是merge中。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def sortList(self, head: ListNode) -> ListNode:

    def merge_two(l1, l2, pre):
        while l1 and l2:
            if l1.val <= l2.val:
                pre.next, l1 = l1, l1.next
            else:
                pre.next, l2 = l2, l2.next
            pre = pre.next
        pre.next = l1 or l2
        while pre.next: pre = pre.next
        return pre

    def cut_list(head, size):
        for i in range(size-1):
            if not head: break
            head = head.next
        if not head: return None
        next_head, head.next = head.next, None  # cut
        return next_head

    dummy = ListNode(0)
    dummy.next, h = head, head
    length, d = 0, 1
    while h:
        h = h.next
        length += 1
    while d < length:
        pre, h = dummy, dummy.next
        while h:
            left = h
            right = cut_list(left, d)
            h = cut_list(right, d)
            pre = merge_two(left, right, pre)
        d *= 2
    return dummy.next

817. Linked List Components

链表的组件。给定一个集合G，然后根据是否在G中分成若干部分，求连起来在G中的部分的个数。原题

1
2
3
4
5
6
Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.
1
2
3
4
5
6
7
8
9
10
11
def numComponents(self, head: ListNode, G: List[int]) -> int:
    SET_G = set(G)
    h = head
    count = 0
    while h:
        if h.val in SET_G:
            if (h.next and h.next.val not in SET_G or 
                not h.next):
                count += 1
        h = h.next
    return count

86. Partition List

链表分区，将比x小的节点放到前面，其余节点放到后面，并保持原有顺序。原题

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

方法一：首次AC的方法。注意最后gt后面可能有残留的节点比如最后一个2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def partition(self, head: ListNode, x: int) -> ListNode:
    lt = letter = ListNode(0)
    gt = greater = ListNode(0)
    h = head
    while h:
        if h.val < x:
            lt.next = h
            lt = h
        else:
            gt.next = h
            gt = h
        h = h.next
    gt.next = None   # important !!
    lt.next = greater.next
    return letter.next

61. Rotate List

向右旋转链表k次。原题

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rotateRight(self, head: ListNode, k: int) -> ListNode:
    n, cur, prev = 0, head, None
    while cur:
        n += 1
        prev, cur = cur, cur.next
    
    if n==0 or k%n==0:
        return head
    k = k % n
    tail = head
    for _ in range(n-k-1):
        tail = tail.next
    ans, tail.next, prev.next = tail.next, None, head
    return ans

725. Split Linked List in Parts

按部分拆分链表。如果不能整除，要保证前面部分的大。原题

1
2
3
4
5
6
Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
    n, cur = 0, root
    ans = []
    while cur:
        n += 1
        cur = cur.next
    parts, remain = divmod(n, k)
    h = root
    for i in range(k):
        head = h
        for i in range(parts-1+(i<remain)):
            h = h.next
        if h:
            h.next, h = None, h.next
        ans.append(head)                            
    return ans

143. Reorder List

1
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def reorderList(self, head: ListNode) -> None:
    if not head:
        return 
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    
    tail, slow.next = slow.next, None
    def reverse(node):
        prev = None
        while node:
            node.next, prev, node = prev, node, node.next
        return prev
    tail = reverse(tail)
    h = head
    while h and tail:
        h.next, tail.next, tail, h = tail, h.next, tail.next, h.next

1030. Next Greater Node In Linked List

链表中下一个比当前节点大的值。和503题类似。原题

1
2
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

方法一：竞赛时没有做出来，虽然是一个链表题，但是跟链表没啥关系。思路vals保存了之前所有节点的值，stack按序存的索引，当遍历一个新的节点时，不断地去和之前的节点比较，如果大于，那么久更新ans中的值，之前设为了0。

1
2
3
4
5
6
7
8
9
10
11
12
13
def nextLargerNodes(self, head: ListNode) -> List[int]:
    stack, vals = [], []
    i, ans = 0, []
    while head:
        num = head.val
        vals.append(num)
        while stack and num > vals[stack[-1]]:
            ans[stack.pop()] = num
        stack.append(i)
        ans.append(0)
        i += 1
        head = head.next
    return ans
方法二：去除方法一中无用的变量。 
1
2
3
4
5
6
7
8
9
def nextLargerNodes(self, head: ListNode) -> List[int]:
    ans, stack = [], []
    while head:
        while stack and stack[-1][1] < head.val:
            ans[stack.pop()[0]] = head.val
        stack.append((len(ans), head.val))
        ans.append(0)
        head = head.next
    return ans

1171. Remove Zero Sum Consecutive Nodes from Linked List

移除相连和为0的节点。像祖玛一样，连续地删除。答案不唯一。原题

1
2
3
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.
方法一：使用字典记录和，当和出现重复的时候，说明其中的一段和为0。看了评论发现此题OJ有错误，[1,3,2,-3,-2,5,5,-5,1]结果为[1,5,5,-5,1]居然对了。 
1
2
3
4
5
6
7
8
9
10
11
12
13
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
    p = dummy = ListNode(0)
    dummy.next = head
    s = 0
    vals = {}
    while p:
        s += p.val
        if s not in vals:
            vals[s] = p
        else:
            vals[s].next = p.next
        p = p.next
    return dummy.next

仔细分析一下上述代码，再结果变成[1,5,5,-5,1]时，没有将vals中删除的节点清空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
    p = dummy = ListNode(0)
    dummy.next = head
    s = 0
    s_sum = [s]
    vals = {}
    while p:
        s += p.val
        s_sum.append(s)
        if s not in vals:
            vals[s] = p
        else:
            vals[s].next = p.next
            s_sum.pop() # remove cur, keep the last
            while s_sum[-1] != s:
                vals.pop(s_sum.pop())
        p = p.next
    return dummy.next

25. Reverse Nodes in k-Group

链表中每k个为一组，反转，要求常数空间复杂度。长度不够则不反转。

1
2
3
4
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

方法一：有点笨，fast指针被修改到前面去了，然后做了补偿，感觉笨笨的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:

    def reverse_node(head, prev):
        h = head
        tail = prev
        while h is not prev:
            h.next, tail, h = tail, h, h.next
        return tail

    dummy = ListNode(0)
    dummy.next = head
    slow = fast = dummy
    for _ in range(k):
        fast = fast.next
        if not fast:
            return dummy.next

    while fast:
        slow.next = reverse_node(slow.next, fast.next)
        for _ in range(k-1):
            fast = fast.next
            if not fast: return dummy.next
        for _ in range(k):
            slow, fast = slow.next, fast.next
            if not fast:
                return dummy.next
方法二：多用点指针。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    dummy = jump = ListNode(0)
    dummy.next = l = r = head

#         def print_node(h):
#             hh = h
#             res = []
#             while hh:
#                 res.append(str(hh.val))
#                 hh = hh.next
#             print('->'.join(res))

    while True:
        count = 0
        while r and count<k:
            r = r.next
            count += 1
        if count == k:
            prev, cur = r, l
            for _ in range(k):
                cur.next, prev, cur = prev, cur, cur.next
            jump.next, jump, l = prev, l, r
        else:
            return dummy.next

###1798. Maximum Number of Consecutive Values You Can Make

使用数组中的任意数组成0开始的连续序列，最多能组成到几。

1
2
3
4
5
6
7
8
9
10
11
12
Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.

方法一：竞赛时最后5分钟绝杀了，排序，按照最小的数开始组，如果连不上，则组不成这个最小的数。

1
2
3
4
5
6
7
def getMaximumConsecutive(self, coins: List[int]) -> int:
    r = 0
    for num in sorted(coins):
        if num > r + 1:
            return r + 1
        r += num
    return r + 1