题解 | #链表中的节点每k个一组翻转# [P3]

两个指针分别指向：
  sentinal: 当前需要反转的k个点的前一个node
  end: 当前需要反转的k个点的随后一个node
  
e.g.:
ans-1-2-3-4-5-6-7-null
s       e

ans-3-2-1-4-5-6-7-null
        s     e
然后对于s->e正常反转链表就行。

import java.util.*;

public class Solution {
  public ListNode reverseKGroup (ListNode head, int k) {
    ListNode ans = new ListNode(0);
    ans.next = head;
    
    // sentinal of the current k group, init to ans.
    ListNode sentinal = ans;
    while (true) {
      ListNode end = sentinal; 
      for (int i = 0; i < k; i++) {
        end = end.next;  // end 
        if (end == null) return ans.next;
      }
      // sentinal.next: start of K group
      // end: end of K group
      sentinal = reverseK(sentinal, end);
    }
  }
  
  public ListNode reverseK(ListNode sentinal, ListNode end) {
    ListNode start = sentinal.next;
    while (sentinal.next != end) {
      ListNode tmp = start.next;
      start.next = tmp.next;
      tmp.next = sentinal.next;
      sentinal.next = tmp;
    }
    
    return start;  // next sentinal
  }
}