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

 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
37
38
39
40
41
42
43
44
45
46

func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k <= 1 {
        return head
    }

    var newHead, lastGroupTail *ListNode

    nextGroupHead := head

    for nextGroupHead != nil {
        right := nextGroupHead

        // search the first node of reversed-group
        for n := 0; n < k-1 && right != nil; n++ {
            right = right.Next
        }

        if right == nil {
            // no more group, so break
            break
        }

        if newHead == nil {
            // first group, set newHead
            newHead = right
        } else {
            // else, link last group and this group
            lastGroupTail.Next = right
        }

        // saving infomation to search next group
        lastGroupTail, nextGroupHead = nextGroupHead, right.Next

        // reversing this group
        left, right := lastGroupTail, nextGroupHead
        for left != nextGroupHead {
            left, left.Next, right = left.Next, right, left
        }
    }

    if newHead == nil {
        return head
    }

    return newHead
}