My accepted solution


  • 0
    A
    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null) {
    			return;
    		}
    
    		ListNode slow = head, fast = head;
    
    		while ((fast.next != null) && (fast.next.next != null)) {
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		
            // Split the list into two halves
    		ListNode secondList = slow.next;
    		slow.next = null;
    		ListNode firstList = head;
    
    		secondList = Solution.ReverseList(secondList);
    		ListNode dummy = new ListNode(Integer.MIN_VALUE);
    		ListNode tail = dummy;
    
            // start merging them using a dummy node
    		while(true){
    			
    			if(firstList == null){
    				tail.next = secondList;
    				break;
    			}
    			else if (secondList == null){
    				tail.next = firstList;
    				break;
    			}
    			else{
                    // just move tail alternatively. Keep track of your pointers though
    				tail.next = firstList;
    				tail = tail.next;
    				firstList = firstList.next;
    				
    				tail.next = secondList;
    				tail = tail.next;
    				secondList = secondList.next;
    			}
    		}
    		
    		head = dummy.next;
        }
        
        public static ListNode ReverseList(ListNode head){
    		
    		if(head == null) return head;
    		ListNode result = null;
    		ListNode current = head;
    		
    		while(current != null){
    			ListNode next = current.next;
    			current.next = result;
    			result = current;
    			current = next;
    		}
    		
    		return result;
    	}
    };

Log in to reply
 

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