Skip to content

Instantly share code, notes, and snippets.

@jingz8804
Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jingz8804/cb2462c7c456cacdf557 to your computer and use it in GitHub Desktop.
Save jingz8804/cb2462c7c456cacdf557 to your computer and use it in GitHub Desktop.
sentinel node is always a good choice if you are confused with the steps you should go.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class ReverseNodesKGroup{
public ListNode reverseKGroup(ListNode head, int k){
if(head == null || k < 2) return head;
// sentinel node is always a good choice if you get confused about the steps you should move.
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode fast = hasNextGroup(sentinel, k);
return reverseKGroup(head, fast, k);
}
private ListNode reverseKGroup(ListNode slow, ListNode fast, int k){
if(fast == null) return slow;
ListNode connect = slow;
ListNode end = null;
ListNode next = null;
while(slow != fast){
next = slow.next;
slow.next = end;
end = slow;
slow = next;
}
fast = hasNextGroup(fast, k);
next = slow.next;
slow.next = end;
connect.next = reverseKGroup(next, fast, k); // connecting with the later reversed nodes
return slow;
}
private ListNode hasNextGroup(ListNode node, int k){
int i = 0;
while(i++ < k && node != null) node = node.next;
return node;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment