[LintCode] 450 Reverse Node in k-Group 解题报告

Description
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



思路
要把整个链表k个k个的翻转，我们就用一个while循环来每次翻转k个node，一直到不能翻转为止。
举个例子k = 2，我们从第二个点开始翻转。
我们首先要判断一下能不能翻k个。如果节点的个数不到k，那么我们就不用翻了。
翻转的时候，我们需要知道被翻转的node的前一个点的信息。比如1 -> 2 -> 3 -> 4 -> 5，要把2和3翻过来，我们需要把翻转好的点先接到1的后面，也就是1 -> 3。然后，翻转完的最后一个点，也要和后面的链表接起来，也就是2 -> 4。最后变成1 -> 3 -> 2 -> 4 -> 5。

每次翻转完，我们要return新的head，以便翻转下一组。

Code

/**
 * 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) {
        // Write your code here
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        head = dummy;
        while (head != null) {
            head = reverseKNodes(head, k);
        }
        
        return dummy.next;
    }
    
    public ListNode reverseKNodes(ListNode head, int k) {
        
        ListNode curr = head.next;
        for (int i = 0; i < k; i++) {
            if (curr == null) {
                return null;
            }
            curr = curr.next;
        }
        
        ListNode prev = null;
        curr = head.next;
        
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        ListNode newHead = head.next;
        head.next.next = curr;
        head.next = prev;
    
        return newHead;
    }
}