Reverse Nodes in k-Group 450

Question

Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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

Solution

思想很简单，就是从第i个元素开始，每次往后走k步，找到第i+k个元素，然后把第i+1个元素到第i+k个元素全部反转相连，最后再将第i个元素和第i+k个元素相连，以及第i+1个元素和第i+k+1个元素相连。再将刚才的第i+1个元素作为新的第“i”个元素重复之前步骤。如果某一次移动不足k次就到尾部，则停止。用符号表示就是Change head->n1->..->nk->next.. to head->nk->..->n1->next..。

反转一个linked list的套路为用三个指针，一个记录pre，一个记录curt，一个记录next，将curt指向pre，然后再将pre，curt，next分别向右移动一步（pre = curt, curt = next, next = next.next）。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @param k an integer
     * @return a ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        head = dummy;
        while (head.next != null) {
            head = reverseNextK(head, k);
        }

        return dummy.next;
    }

    // reverse head->n1->..->nk->next..
    // to head->nk->..->n1->next..
    // return n1
    private ListNode reverseNextK(ListNode head, int k) {
        // check there is enought nodes to reverse
        ListNode next = head; // next is not null
        for (int i = 0; i < k; i++) {
            if (next.next == null) {
                return next;
            }
            next = next.next;
        }

        // reverse
        ListNode n1 = head.next;
        ListNode prev = head, curt = n1;
        for (int i = 0; i < k; i++) {
            ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }

        n1.next = curt;
        head.next = prev;
        return n1;
    }
}