Simple Java Solution O(n)


  • 0
    N

    Reversing K elements at a time and moving forward

    Steps
    1.We have created a method reverseSubList which reverse the sublist and return new head.
    2.Our main method calls reverseSubList each time with new head moving K time forward and join returned new headwith previously saved tail .
    3.We keep doing this in loop and each time subtracting K from the original length .
    4.Logic will keep running till the time we have enough element remaining in the list i.e. > K

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
    
    /**
     * 
     * @param head HeadNode of input list
     * @param k reverse the nodes of a linked list k at a time
     * @return head of final resultant link list
     */
    	public  ListNode reverseKGroup(ListNode head, int k) {
    
    		ListNode currentSubListHead = head;
    		ListNode headOfLastReversedSubList = null;
    		ListNode tailOfLastReversedSubList = null;
    		int length = lengthFromNode(currentSubListHead);
    		while (currentSubListHead != null && length >= k && k > 1) {
    
    			ListNode headNodeForNextSubList = currentSubListHead;
    			int i = 1;
    			
    			//Below while will save the head for next sublist to get reversed;
    			while (headNodeForNextSubList != null && i <= k) {
    				i++;
    				if (headOfLastReversedSubList == null) {
    					head = headNodeForNextSubList;
    				}
    				headNodeForNextSubList = headNodeForNextSubList.next;
    			}
    			headOfLastReversedSubList = reverseSubList(currentSubListHead, k);
    			if (tailOfLastReversedSubList == null) {
    				tailOfLastReversedSubList = headOfLastReversedSubList;
    			} else {
    				tailOfLastReversedSubList.next = headOfLastReversedSubList;
    			}
    
    			while (headOfLastReversedSubList != null && headOfLastReversedSubList.next != null) {
    				headOfLastReversedSubList = headOfLastReversedSubList.next;
    			}
    			tailOfLastReversedSubList = headOfLastReversedSubList;
    			currentSubListHead = headNodeForNextSubList;
    			length =length-k;
    		}
    		
    		//Below if will add the remaining elements(whose count is less than K) to last reversed sub list tail 
    		if (tailOfLastReversedSubList != null) {
    			tailOfLastReversedSubList.next = currentSubListHead;
    		}
    		return head;
    
    	}
    
    	/**
    	 * @param sublistHead
    	 *            head node of sublist
    	 * @param k
    	 *            integer determining sublist
    	 * @return new head of reversed sublist
    	 */
    	private  ListNode reverseSubList(ListNode sublistHead, int k) {
    		int counter = 0;
    		ListNode resumeNode = null;
    		ListNode previous = null;
    		while (counter < k - 1 && sublistHead != null && sublistHead.next != null) {
    			// Reversing pointer for two consecutive node
    			ListNode temp = sublistHead.next;
    			resumeNode = temp.next;
    			sublistHead.next.next = sublistHead;
    			sublistHead.next = previous;
    
    			previous = temp;
    			sublistHead = resumeNode;
    			counter = counter + 2;
    		}
    		 
    		//this condition will take care of last node if K is odd number
    		if (sublistHead != null && counter == (k - 1)) {
    
    			sublistHead.next = previous;
    			previous = sublistHead;
    
    		}
    		return previous;
    
    	}
    
    	/**
    	 * @param node
    	 *            to calculate the length
    	 * @return length of the list from the node
    	 */
    	private  int lengthFromNode(ListNode node) {
    		ListNode temp = node;
    		int result = 0;
    		while (temp != null) {
    			result++;
    			temp = temp.next;
    		}
    		return result;
    	}
    }
    

Log in to reply
 

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