Leetcode discuss: 143. Reorder List

Here is the link.

C# Slow and fast two runners and a stack story about linked list

July 14, 2020

143. Reorder List

Introduction
It is the second algorithm in my Leetcode mock interview. I did not have time to write the code, there are three algorithms, 90 minutes. I spent near 40 minutes on the first algorithm. and I did not have enough time to complete the code. 463. Island Perimeter is the first algorithm.

My performance goal
I am preparing for July 20, 2020 Facebook phone screen. I like to write the code with bug free in less than 20 minutes.
I just finished two linkedlist practice, one is called find loop start in looped linked list, and then second one is to merge two linked list. So I learned the lesson how to avoid the bugs in the linked list problem solving. I wrote those two algorithms since those are my previous Leetcode mock interview phone screen algorithms in the same day.

142 Linked List Cycle II
328 Odd Even Linked List

How to solve the problem?
The idea is to run the slow and fast two runners to find second half start node in the linked list, and then iterate all nodes in the linked list into a stack.

Next is to merge node from first half and node from stack into a new linked list.

The challenge
I did not practice Leetcode very often from January to May 2020, so it takes me some time to figure out how to write basic things like linked list or other challenging solutions.

In order to push myself hard, I do think that I need to change my mindset. As a software programmer, I do not have to practice algorithms every day. But it is big risk since I do not have enough challenge and therefore I can say that I waste a lot of time.

My argument is this. In order to be a competitive programmer, I should think about building good habit to code every day.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _143_reorder_list
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        public class ListNode {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }

        /// <summary>
        /// 143 reorder list 
        /// 1 -> 2 ->3 ->4 ->5
        /// result 1 ->5 ->2 ->4 -> 3
        /// next half reversed and then mix with the first half
        /// </summary>
        /// <param name="head"></param>
        public void ReorderList(ListNode head)
        {
            if (head == null)
                return;            

            var slow = head;
            var fast = head;

            while (fast != null)
            {
                if (fast.next == null)
                {
                    break;
                }

                fast = fast.next.next;
                slow = slow.next;
            }

            var reserve = slow.next;
            slow.next = null;

            var reverse = reserve;
            var stack = new Stack<ListNode>(); 

            while (reverse != null)
            {
                var copy = reverse.next;
                reverse.next = null;  // break the link please

                stack.Push(reverse);

                reverse = copy; 
            }

            // mix linked list with the nodes in the stack
            var headCopy = head;

            while (headCopy != null && stack.Count > 0)
            {
                var copy = headCopy.next;
                headCopy.next = null;

                var pop = stack.Pop();
                headCopy.next = pop;

                pop.next = copy;

                // next iteration
                headCopy = copy; 
            }            
        }
    }
}