LeetCode 25 - Reverse Nodes in k-Group

https://leetcode.com/problems/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.

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 kthen left-out nodes in the end should remain as it is.

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

X.
http://bangbingsyb.blogspot.com/2014/11/leetcode-reverse-nodes-in-k-group.html
Swap Nodes in Pairs那题的升级版，算linked list指针操作题中难度最高最容易写错的之一。思路很简单，就是每次反转k个节点，如果还没反转到i<k个节点就遇到尾部了，则将这i个节点再反转回来。但要短时间内写正确却难度不小。这类题目一定要画图来验证解法是否正确。

几乎用到linked list题所有的技巧。

1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。

2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。

3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。注意，要反转k个节点的话，实际反转指针只需要k-1次。

4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回，并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。

5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。

    ListNode *reverseKGroup(ListNode *head, int k) {
        if(k<2) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p = dummy;
        while(p->next && p->next->next) {
            ListNode *prev = p->next, *cur = prev->next;
            int i=0;
            while(cur && i<k-1) {
                ListNode *temp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = temp;
                i++;
            }
            
            if(i==k-1) {    // k nodes reversed
                ListNode *temp = p->next;
                p->next->next = cur;
                p->next = prev;
                p = temp;
            }
            else {  // less than k nodes reversed before reach end
                cur = prev->next;
                prev->next = NULL;
                while(cur != p->next) {
                    ListNode *temp = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur = temp;
                }
                break; 
            }
        }
        return dummy->next;
    }

https://zxi.mytechroad.com/blog/list/leetcode-25-reverse-nodes-in-k-group/

  ListNode *reverseKGroup(ListNode *head, int k) {

    if (!head || k == 1) return head;

    ListNode dummy(0);

    dummy.next = head;

    int len = 1;

    while (head = head->next) len++;

    ListNode* pre = &dummy;    

    for (int l = 0; l + k <= len; l += k) {

      ListNode* cur = pre->next;

      ListNode* nxt = cur->next;

      for (int i = 1; i < k; ++i) {

        cur->next = nxt->next;

        nxt->next = pre->next;

        pre->next = nxt;

        nxt = cur->next;

      }

      pre = cur;

    }

    return dummy.next;

  }

http://www.cnblogs.com/grandyang/p/4441324.html

这道题让我们以每k个为一组来翻转链表，实际上是把原链表分成若干小段，然后分别对其进行翻转，那么肯定总共需要两个函数，一个是用来分段的，一个是用来翻转的，我们就以题目中给的例子来看，对于给定链表1->2->3->4->5，一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node，那么我们加入dummy node后的链表变为-1->1->2->3->4->5，如果k为3的话，我们的目标是将1,2,3翻转一下，那么我们需要一些指针，pre和next分别指向要翻转的链表的前后的位置，然后翻转后pre的位置更新到如下新的位置：

-1->1->2->3->4->5

 |        |  |
pre      cur next

-1->3->2->1->4->5
    |     |  |
   cur   pre next

以此类推，只要cur走过k个节点，那么next就是cur->next，就可以调用翻转函数来进行局部翻转了，注意翻转之后新的cur和pre的位置都不同了，那么翻转之后，cur应该更新为pre->next，而如果不需要翻转的话，cur更新为cur->next：

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11413/Share-my-Java-Solution-with-comments-in-line

        public ListNode reverseKGroup(ListNode head, int k) {
            if (head==null||head.next==null||k<2) return head;
    
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            
            ListNode tail = dummy, prev = dummy,temp;
            int count;
            while(true){
                count =k;
                while(count>0&&tail!=null){
                    count--;
                    tail=tail.next;
                } 
                if (tail==null) break;//Has reached the end
                
    
                head=prev.next;//for next cycle
            // prev-->temp-->...--->....--->tail-->....
            // Delete @temp and insert to the next position of @tail
            // prev-->...-->...-->tail-->head-->...
            // Assign @temp to the next node of @prev
            // prev-->temp-->...-->tail-->...-->...
            // Keep doing until @tail is the next node of @prev
                while(prev.next!=tail){
                    temp=prev.next;//Assign
                    prev.next=temp.next;//Delete
                    
                    temp.next=tail.next;
                    tail.next=temp;//Insert
                    
                }
                
                tail=head;
                prev=head;
                
            }
            return dummy.next;
            
        }

https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea

First, build a function reverse() to reverse the ListNode between begin and end. See the explanation below:

   /**
     * Reverse a link list between begin and end exclusively
     * an example:
     * a linked list:
     * 0->1->2->3->4->5->6
     * |           |   
     * begin       end
     * after call begin = reverse(begin, end)
     * 
     * 0->3->2->1->4->5->6
     *          |  |
     *      begin end
     * @return the reversed list's 'begin' node, which is the precedence of node end
     */

Then walk thru the linked list and apply reverse() iteratively. See the code below.

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode begin;
    if (head==null || head.next ==null || k==1)
    	return head;
    ListNode dummyhead = new ListNode(-1);
    dummyhead.next = head;
    begin = dummyhead;
    int i=0;
    while (head != null){
    	i++;
    	if (i%k == 0){
    		begin = reverse(begin, head.next);
    		head = begin.next;
    	} else {
    		head = head.next;
    	}
    }
    return dummyhead.next;
    
}

public ListNode reverse(ListNode begin, ListNode end){
	ListNode curr = begin.next;
	ListNode next, first;
	ListNode prev = begin;
	first = curr;
	while (curr!=end){
		next = curr.next;
		curr.next = prev;
		prev = curr;
		curr = next;
	}
	begin.next = prev;
	first.next = curr;
	return first;
}

X.
我们也可以使用递归来做，我们用head记录每段的开始位置，cur记录结束位置的下一个节点，然后我们调用reverse函数来将这段翻转，然后得到一个new_head，原来的head就变成了末尾，这时候后面接上递归调用下一段得到的新节点，返回new_head即可

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *cur = head;
        for (int i = 0; i < k; ++i) {
            if (!cur) return head;
            cur = cur->next;
        }
        ListNode *new_head = reverse(head, cur);
        head->next = reverseKGroup(cur, k);
        return new_head;
    }
    ListNode* reverse(ListNode* head, ListNode* tail) {
        ListNode *pre = tail;
        while (head != tail) {
            ListNode *t = head->next;
            head->next = pre;
            pre = head;
            head = t;
        }
        return pre;
    }

https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
https://www.geeksforgeeks.org/reverse-linked-list-groups-given-size-set-2/
https://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11423/Short-but-recursive-Java-code-with-comments

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count != k) { // find the k+1 node
        curr = curr.next;
        count++;
    }
    if (count == k) { // if k+1 node is found
        curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
        // head - head-pointer to direct part, 
        // curr - head-pointer to reversed part;
        while (count-- > 0) { // reverse current k-group: 
            ListNode tmp = head.next; // tmp - next head in direct part
            head.next = curr; // preappending "direct" head to the reversed list 
            curr = head; // move head of reversed part to a new node
            head = tmp; // move "direct" head to the next node in direct part
        }
        head = curr;
    }
    return head;
}

https://www.jiuzhang.com/solution/reverse-nodes-in-k-group/

    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;
    }

1