Merge Solution - Reorder a LinkedList - Reference

The tough part of this problem is the reference. Pass by reference is a headache.

The basic idea is to find the second half Head, then reverse it… merge two sub list. The reference will be the key point… in reverse function and merge function… need to be super careful ...


/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return;
        }
        ListNode secondHead = head;
        ListNode oneStepNode = head;
        ListNode secondStepNode = head;
       
        while(secondStepNode != null && secondStepNode.next != null){
            secondStepNode = secondStepNode.next.next;
            oneStepNode = oneStepNode.next;
        }
        secondHead = oneStepNode.next;
        oneStepNode.next = null;
       
        secondHead = reverseList(secondHead);
       
        mergeList(head, secondHead);
    }
   
    private ListNode reverseList(ListNode node) {
        if(node.next == null){
            return node;
        }
        ListNode loop = node.next;
        ListNode newHead = new ListNode(node.val);
        while(loop != null){
            ListNode temp = loop.next;
            loop.next = newHead;
            newHead = loop;
            loop = temp;
        }
        return newHead;
    }
   
    private void mergeList(ListNode firstHead, ListNode secondHead){
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode loopNode = newHead;
        while(firstHead !=null && secondHead != null){
            loopNode.next = firstHead;
            firstHead = firstHead.next;
            loopNode = loopNode.next;
            loopNode.next = secondHead;
            secondHead = secondHead.next;
            loopNode = loopNode.next;
        }
        if(firstHead != null){
            loopNode.next = firstHead;
        }
        firstHead = newHead.next;
    }
}