Reverse Nodes in k-Group

Description

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

将链表按长度k分组并反转

Solution

 1func reverseKGroup(head *ListNode, k int) *ListNode {
 2    if head == nil || k <= 1 {
 3        return head
 4    }
 5
 6    var newHead, lastGroupTail *ListNode
 7
 8    nextGroupHead := head
 9
10    for nextGroupHead != nil {
11        right := nextGroupHead
12
13        // search the first node of reversed-group
14        for n := 0; n < k-1 && right != nil; n++ {
15            right = right.Next
16        }
17
18        if right == nil {
19            // no more group, so break
20            break
21        }
22
23        if newHead == nil {
24            // first group, set newHead
25            newHead = right
26        } else {
27            // else, link last group and this group
28            lastGroupTail.Next = right
29        }
30
31        // saving infomation to search next group
32        lastGroupTail, nextGroupHead = nextGroupHead, right.Next
33
34        // reversing this group
35        left, right := lastGroupTail, nextGroupHead
36        for left != nextGroupHead {
37            left, left.Next, right = left.Next, right, left
38        }
39    }
40
41    if newHead == nil {
42        return head
43    }
44
45    return newHead
46}