Good modular java solution with comments.


  • 0
    P
    public void reorderList(ListNode head) { //works close to in O(N)
    		if (head == null || head.next == null)
    			return;
    		ListNode dummy = new ListNode(0);
    		dummy.next = head;
    		ListNode slow = dummy;
    		ListNode fast = slow;
    
    		while (fast != null && fast.next != null) {
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		fast = slow;
    		while (fast.next != null) 
    			fast = fast.next;
    		reverse(slow.next);     // Reverse the second half
    		slow.next = null;        //cut the list in half.
    		slow = head;
    
    		while (slow != null && fast != null) {    // set next of current node to last and so on.
    			ListNode Snext = slow.next;
    			ListNode Fnext = fast.next;
    			slow.next = fast;
    			slow = Snext;
    			fast.next = Snext;
    			fast = Fnext;
    
    		}
    
    	}
    
    	private void reverse(ListNode head) { // Fancy way to reverse a linked list. O(N) space though.
    		if (head == null || head.next == null)
    			return;
    		reverse(head.next);
    		head.next.next = head;
    		head.next = null;
    
    	}
    

Log in to reply
 

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