using System;

using System.Text;

​

public class Program

{

    /*

    You are given the head of a singly linked-list.

The positions of a linked list of length = 7 for example, can intially be represented as:

[0, 1, 2, 3, 4, 5, 6]

Reorder the nodes of the linked list to be in the following order:

[0, 6, 1, 5, 2, 4, 3]

Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:

[0, n-1, 1, n-2, 2, n-3, ...]

You may not modify the values in the list's nodes, but instead you must reorder the nodes themselves.

Example 1:

Input: head = [2,4,6,8] */

    // * Definition for singly-linked list.

  public class ListNode {

      public int val;

      public ListNode next;

      public ListNode(int val=0, ListNode next=null) {

          this.val = val;

          this.next = next;

      }

  } 

​

    public static void Main()

    {       

        ListNode node0 = new ListNode(0);       

        ListNode node1 = new ListNode(1);

        ListNode node2 = new ListNode(2);

        ListNode node3 = new ListNode(3);

        ListNode node4 = new ListNode(4);

        ListNode node5 = new ListNode(5);

        node0.next = node1;

        node1.next = node2;

        node2.next = node3;

        node3.next = node4;

        node4.next = node5;

        PrintList(node0);

        ListNode reversed = ReorderList(node0);

        Console.WriteLine("ans:");

        PrintList(reversed);

    }

​

    public static void PrintList(ListNode node)

    {

        StringBuilder sb = new StringBuilder();

        while(node != null)

        {

            sb.Append(node.val);

            if(node.next != null)

            {

                sb.Append(" -> ");

            }

            node = node.next;

        }

        Console.WriteLine(sb.ToString());

    }

​

    public static ListNode ReorderList(ListNode node)

    {

        // Find middle

        ListNode slow = node;

        ListNode fast = node;

        // fast hasn't reached the end

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

        {

            // Move slow by one place

            slow = slow.next;

            // Move fast by two places

            fast = fast.next.next;

        }

        //return slow;

        // Here slow will be pointing to the start of second list which starts from the middle.     

        ListNode second = slow;     

        // Reverse the second List. 

        // Use three pointers - prev, current, next. 

        // 0     1 ->  2    -> 3 -> 4  

        // prev  c    next

        // 0 <-  1 ->  2    -> 3 -> 4  

        //            prev     c    next

        ListNode prev = null;

        ListNode current = second;

        ListNode next;

        while(current != null)

        {

            next = current.next;                // store the next pointer so we can come back to it later.

            current.next = prev;                // point current to prev so as to reverse

            prev = current;                     // prev takes old position of current

            current = next;                     // current takes old position of next, saved in first step.

        }

        // When current is null, prev will have the pointer to the head of the second list which is now reversed.

        ListNode current1 = node.next; // this is the beginning of the first list.

        ListNode current2 = prev; // you can assign slow to this as well.

        // Merge two lists

        // You have two lists // current1 and current2 // if they are not sorted, use counter, and parity == 0 or 1 to alternate

        ListNode tail = node;

        int count = 0;

        while(current1 != null && current2 != null)

        {

            if(count % 2 == 0)

            {

                tail.next = current2;

                current2 = current2.next;

            }

            else 

            {

                tail.next = current1;

                current1 = current1.next;               

            }

            tail = tail.next;

            count += 1;

        }

        return node;

    }

}

​