25. Reverse Nodes in k-Group

Leetcode Linked List

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.

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

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

分析

一种直接的方法就是对每$k$个元素，依次进行反转，反转的方法可以参考LeetCode-Q206ReverseLinkedList.

public ListNode reverseKGroup(ListNode head, int k) {
    if ((head==null) || (head.next == null) || (k == 1)) {
        return head;
    }
    ListNode pos = head;
    ListNode cur;
    ListNode prev;
    ListNode next;
    ListNode last = head;

    // find the length of the linked list
    int len;
    for (len = 1; pos.next!= null; len++) pos = pos.next;

    pos = head;
    // reverse
    for (int i = 0; i < len/k; i++) {
        cur = pos.next;
        prev = pos;
        // reverse each k nodes
        for (int j = 0; j < k-1; j++) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        if (i == 0) {
            head = prev;
        }  else {
            last.next = prev;
        }

        last = pos;
        pos.next = cur;
        pos = cur;
    }
    return head;
}

Python

def reverseKGroup(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    # 特殊情况
    if k < 2:
        return head

    newhead = ListNode(0)
    newhead.next =  head
    results = newhead

    while 1:

        before = newhead
        # 前进k步
        count = 0
        tmp = []
        while newhead.next  and count < k:
            newhead = newhead.next
            tmp.append(newhead)
            count += 1

        # 判断退出条件
        if count != k:
            return results.next

        # 反转
        after = newhead.next
        tmp[0].next = after
        before.next = tmp[k-1]
        for i in reversed(range(1, k)):
            tmp[i].next = tmp[i-1]
        newhead = tmp[0]

    return results.next