LeetCode 25 Reverse Nodes in k-Group

Posted on | In | 阅读

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 nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Leetcode 24的扩展版，k个一组进行翻转，最后不到k个的不翻转

没轮一共翻转k-1次，每次都将后一个node连到已经连好的链的最前面，已经连好的链首节点之前的一个节点和尾节点两个节点标记为root、head

Python Code

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        res = root = ListNode(-1)
        root.next = head
        tmp = head
        cnt = 0
        while(tmp != None):
            tmp = tmp.next
            cnt += 1
        while(cnt >= k):
            for i in range(k-1):
                node = root.next
                root.next = head.next
                head.next = root.next.next
                root.next.next = node
            root = head
            head = head.next
            cnt -= k
        return res.next