LeetCode Reverse Nodes in k-Group

LeetCode解題之Reverse Nodes in k-Group

原題

將一個鏈表中每k個數進行翻轉，末尾不足k個的數不做變化。

注意點：

例子：

輸入: head = 1->2->3->4->5, k = 2
輸出: 2->1->4->3->5

輸入: head = 1->2->3->4->5, k = 3
輸出: 3->2->1->4->5

解題思路

這個題是Swap Nodes in Pairs的升級版。我們來看一下翻轉k個節點要進行哪些操作，A->B->C->D->E，現在我們要翻轉BCD三個節點。進行以下幾步：

上面做了兩件事，把k個節點先翻轉（1、2兩步），再和前後兩個節點連接起來（3、4兩步）。

AC源碼

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or k <= 1:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        temp = dummy
        while temp:
            temp = self.reverseNextK(temp, k)
        return dummy.next

    def reverseNextK(self, head, k):
        # Check if there are k nodes left
        temp = head
        for i in range(k):
            if not temp.next:
                return None
            temp = temp.next

        # The last node when the k nodes reversed
        node = head.next
        prev = head
        curr = head.next
        # Reverse k nodes
        for i in range(k):
            nextNode = curr.nex
            curr.next = prev
            prev = curr
            curr = nextNode
        # Connect with head and tail
        node.next = curr
        head.next = prev
        return node

歡迎查看我的Github來獲得相關源碼。