Skip to content

25. Reverse Nodes in k Group

Linjie Pan edited this page Apr 8, 2019 · 1 revision
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode fakeHead = new ListNode(-1); // fake head can simplify the reverse process
    fakeHead.next = head; // fake head point to the head of linkedlist
    ListNode last = fakeHead; // last is the tail node of the reversed part, which is fakeHead in the beginning
    ListNode nextLast = head; // nextLast is the head node of the remained part, which is head in the beginning
    ListNode current = head; // current is the current node to be reversed, which is head in the beginning
    ListNode prev = null; // prev is the last node that has been reversed
    while( current != null ) {
        int i = 1;
	ListNode countNode = current;
	int count = 0;
	while( countNode != null ) {
	    count++;
	    countNode = countNode.next;
	}
	if( count < k ) {
	    last.next = current;
	    break;
        }
	while( i <= k ) {
	    ListNode next = current.next;
	    current.next = prev;
	    prev = current;
	    current = next;
	    i++;
	}
	last.next = prev;
	last = nextLast;
	nextLast = current;
	prev = null;
    }
    return fakeHead.next;
}
Clone this wiki locally