Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

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.

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

leetcode大牛的O(n)做法

因为是翻转k个node,所以我们可以单独处理这部分。reverse(ListNode pre,ListNode next)方法逆置了pre和next之间的节点,并返回了下次的pre节点。

an example:
a linked list:
0->1->2->3->4->5->6
| | 
pre next
after call pre = reverse(pre, next)
0->3->2->1->4->5->6
| |
pre next

主方法里面通过用i计数,每次到达k个节点,就调用reverse方法逆转。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || k == 1){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next= head;
        ListNode pre = dummy;
        int i = 0;
        while(head != null){
            i++;
            if(i % k == 0){
                pre = reverse(pre,head.next);
                head = pre.next; // 链表的结构已改变
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }
    
    // 翻转pre到next之间的节点(不包括pre和next)
    private ListNode reverse(ListNode pre,ListNode next){
        ListNode last = pre.next;
        ListNode cur = last.next;
        while(cur != next){
            last.next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = last.next;
        }
        return last;
    }
}