動機

之前寫的很爛，居然還用到例外!? 所以重寫

Problem

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

 

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

Input: head = [1], k = 1Output: [1]

 

Constraints:

  • The number of nodes in the list is in the range sz.
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

 

Follow-up: Can you solve the problem in O(1) extra memory space?

Sol

這題其實把reverse，a到b的部分寫出來就幾乎完成了，可以看這裡有解釋

剩下就是把group的起終點找出來再丟到reverse就ok了

def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
    def rev(a,b): # [a,b)
        ptr = a
        ptr_next = a.next
        a.next = None
        while ptr_next is not b:
            tmp = ptr_next.next
            ptr_next.next = ptr
            ptr = ptr_next
            ptr_next = tmp
        return [ptr,a] # head, tail
    group_head = head
    prev_group_tail = None
    ret = None
    while group_head:
        group_tail = group_head
        for _ in range(k):
            if not group_tail:
                return ret if ret else head
            else:
                group_tail = group_tail.next
        h,d = rev(group_head,group_tail)
        if not ret:
            ret = h
        else:
            prev_group_tail.next = h
        d.next = group_tail
        group_head = group_tail
        prev_group_tail = d
    return ret