Reorder List

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

Example:

Given 1->2->3->4, reorder it to 1->4->2->3.

Approach: We can maintain a stack to get the nodes in the reverse order and we can have a iterator starting from head. We can keep merging these nodes till the iterator and top of stack are same or iterator's next and top of stack are same. Here is the code -

        public void ReorderList1()

        {

            if (this.Head == null || this.Head.Next == null)

            {

                return;

            }

            Stack<LinkedListNode> stack = new Stack<LinkedListNode>();

            LinkedListNode itr = this.Head;

            while (itr != null)

            {

                stack.Push(itr);

                itr = itr.Next;

            }

            itr = this.Head;

            LinkedListNode itrEnd = stack.Pop();

            while(itr != itrEnd && itr.Next != itrEnd)

            {

                LinkedListNode tempNext = itr.Next;

                itr.Next = itrEnd;

                itrEnd.Next = tempNext;

                itr = tempNext;

                itrEnd = stack.Pop();

            }

            if (itr == itrEnd)

            {

                itr.Next = null;

            }

            else 

            {

                itrEnd.Next = null;

            }

        }

Complexity: O(n)

Even the above approach runs in O(n) but it has the space complexity of O(n). Can we do better? If we look at the approach closely, we can see we are reversing the second half of the list and merging. So we can do it without stack now. Here is the optimized solution -

        public void ReorderList()

        {

            if (this.Head == null || this.Head.Next == null)

            {

                return;

            }

            LinkedListNode slow = this.Head, fast = this.Head.Next;

            // Getting the mid element

            while (fast != null)

            {

                slow = slow.Next;

                fast = fast.Next;

                if (fast != null)

                {

                    fast = fast.Next;

                }

            }

            // Reversing the second half

            fast =  this.ReverseFromNode(slow.Next);

            slow.Next = null;

            slow = this.Head;

            // Merging now

            while(fast != null) // second half will be less than or equal to the first half

            {

                LinkedListNode tempNext = slow.Next;

                LinkedListNode tempFastNext = fast.Next;

                slow.Next = fast;

                fast.Next = tempNext;

                fast = tempFastNext;

                slow = tempNext;

            }

        } 

Complexity: O(n)