Last active
August 29, 2015 14:01
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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