LeetCode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:

We divide the list in two parts for instance 1->2->3->4->5 will become 1->2->3 and 4->5, we have to reverse the second list and give a list that alternates both. The split is done with a slow and fast pointer.

First solution (using a stack for reversing the list):

public class Solution {

    public void reorderList(ListNode head) {

        if(head == null)

            return;

        ListNode slowPointer = head;

        ListNode fastPointer = head.next;

        while(fastPointer!=null && fastPointer.next !=null)

        {

            fastPointer = fastPointer.next.next;

            slowPointer = slowPointer.next;

        }

        ListNode head2 = slowPointer.next;

        slowPointer.next = null;

        LinkedList<ListNode> queue = new LinkedList<ListNode>();

        while(head2!=null)

        {

            ListNode temp = head2;

            head2 = head2.next;

            temp.next =null;

            queue.push(temp);

        }

        while(!queue.isEmpty())

        {

            ListNode temp = queue.pop();

            temp.next = head.next;

            head.next = temp;

            head = temp.next;

        }

    }

}

Second solution (no data structure allowed):

public class Solution {

    public void reorderList(ListNode head) {

        if(head == null)

            return;

        ListNode slowPointer = head;

        ListNode fastPointer = head.next;

        while(fastPointer!=null && fastPointer.next !=null)

        {

            fastPointer = fastPointer.next.next;

            slowPointer = slowPointer.next;

        }

        ListNode head2 = slowPointer.next;

        slowPointer.next = null;

        head2= reverseList(head2);

        alternate (head, head2);

    }

    

    private ListNode reverseList(ListNode head)

    {

        if (head == null)

            return null;

        ListNode reversedList = head;

        ListNode pointer = head.next;

        reversedList.next=null;

        while (pointer !=null)

        {

            ListNode temp = pointer;

            pointer = pointer.next;

            temp.next = reversedList;

            reversedList = temp;

        }

        return reversedList;

    }

    

    private void alternate (ListNode head1, ListNode head2)

    {

        ListNode pointer = head1;

        head1 = head1.next;

        boolean nextList1 = false;

        while(head1 != null || head2 != null)

        {

            if((head2 != null && !nextList1) || (head1==null))

            {

                pointer.next = head2;

                head2 = head2.next;

                nextList1 = true;

                pointer = pointer.next;

            }

            else 

             {

                pointer.next = head1;

                head1 = head1.next;

                nextList1 = false;

                pointer = pointer.next;

            }

        }

    }

}