My recursive and iterative Java solution


  • 0
    F

    Recursive:

    public ListNode reverseKGroup(ListNode head, int k) {
    	ListNode newHead = head;
    	for (int i = 0; i < k; i++) {
    		if (newHead == null)
    			return head;
    		newHead = newHead.next;
    	}
    	ListNode tail = head;
    	ListNode p = tail.next;
    	while (p != newHead) {
    		tail.next = p.next;
    		p.next = head;
    		head = p;
    		p = tail.next;
    	}
    	tail.next = reverseKGroup(newHead, k);
    	return head;
    }
    

    Iterative:

    public ListNode reverseKGroup(ListNode head, int k) {
    	ListNode dummy = new ListNode(0);
    	dummy.next = head;
    	ListNode tail = head;
    	head = dummy;
    	ListNode nextTail = tail;
    	mainLoop: while (tail != null) {
    		for (int i = 0; i < k; i++) {
    			if (nextTail == null)
    				break mainLoop;
    			nextTail = nextTail.next;
    		}
    
    		ListNode p = tail.next;
    		while (p != nextTail) {
    			tail.next = p.next;
    			p.next = head.next;
    			head.next = p;
    			p = tail.next;
    		}
    		head = tail;
    		tail = nextTail;
    	}
    	return dummy.next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.