## Question

>[Leetcode.143 Reorder List
](https://leetcode.com/problems/reorder-list/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
- an intuitive solution
:::spoiler Code

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  /**
        1 2 3 4 5 

        1 2
        3 4 5 

        1 2
        5 4 3

        1 5 2 4 3      
     */

  let dummy = new ListNode(0, head);
  let slow = dummy;
  let fast = dummy;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if (slow === fast) return head; // the edge case: [1]

  fast = slow.next;
  slow.next = null;
  slow = head;

  /**
       reve curr next
             4 -> 5 -> 6
        n <- 4 <- 5 <- 6

            reve fast
            curr next
        n <- 4 <- 5 <- 6

                reve fast
                curr next
        n <- 4 <- 5 <- 6

     */

  let reversed = null;
  while (fast) {
    let curr = fast; // 4
    let next = fast.next; // 5
    curr.next = reversed; // reve <- 4
    reversed = curr; // 4
    fast = next; // 5
  }

  /**
        1 2
        5 4 3

        1 5 2 4 3
    */
  let newCurr = slow;
  while (newCurr) {
    const currNext = newCurr.next;
    const reversedNext = reversed.next;
    newCurr.next = reversed;
    if (currNext) reversed.next = currNext;
    newCurr = currNext;
    reversed = reversedNext;
  }
  return slow;
};

:::

<hr/>

### Sol

1. (Fast-Slow pointer) Find out the middle of the linked list
2. At the middle of the linked list, separate it into two linked lists
3. Reverse the pointer of the second linked list
4. Merge the two linked lists

:::spoiler Code

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    // Find out the middle of the linked list
    let slowPointer = head;
    let fastPointer = head;
    let secoundLinkedListHead = null;
    while(fastPointer) {
        if(!fastPointer.next || !fastPointer.next.next){
            // At the middle of the linked list, separate it into two linked lists
            secoundLinkedListHead = slowPointer.next;
            slowPointer.next = null;
            fastPointer= null
        }else{
            fastPointer = fastPointer.next.next;
        }
        slowPointer = slowPointer.next;
    }
    
    // Reverse the pointer of the second linked list
    let pre = null;
    let cur = secoundLinkedListHead;
    let next = null;
    while(cur){
        next = cur.next;
        cur.next = pre;
        pre = cur
        cur = next 
    }

    // Merge the two linked lists
    let curFirst = head;
    let curSecound = pre; // right head
    let tempFirst = null;
    let tempSecound = null;
 
    while(curFirst && curSecound){
        tempFirst = curFirst.next;
        tempSecound = curSecound.next;
        curFirst.next = curSecound;
        curSecound.next = tempFirst
        curFirst = tempFirst;
        curSecound = tempSecound
    }
};

:::

<hr/>

### 東
~~*Not sure if this is a allowed approach...*~~
(好的... 我最後意識到這是一個 space `O(n)` 的解法)

**Modify given singly linked list into a doubly linked list in order to traverse backwards**


- 1st loop
- Connect `prev` pointer
- Calculate total nodes count

- 2nd loop:
- Use front pointer and back pointer to track nodes to connect
- Remove added `prev` pointer

:::spoiler Code

// Time - O(n) | Space - O(n)

var reorderList = function(head) {
    if(!head.next) {
        return head;
    }

    let prevNode = head;
    let currNode = head.next;
    let nodeCount = 1;
    while (!!currNode) {
        currNode.prev = prevNode;
        prevNode = prevNode.next;
        currNode = currNode.next;
        nodeCount++;
    }

    let currBack = prevNode;
    let nextBack = prevNode.prev;
    let currFront = head;
    let nextFront = head.next;
    let nodeToConnect = nodeCount - 1;
    
    while(nodeToConnect > 0) {
        currBack.next = null;
        currFront.next = currBack;
        nodeToConnect--;
        
        if(nodeToConnect === 0) {
            break;
        }

        currFront = nextFront;
        nextFront = nextFront.next;
        
        currFront.next = null;
        currBack.next = currFront;
        nodeToConnect--;

        currBack = nextBack;
        nextBack = nextBack.prev;

        delete nextFront.prev;
        delete currBack.prev;
    }
};

:::

<hr/>

### Jessie


:::spoiler Code

var reorderList = function (head) {
  if (!head.next || !head.next.next) return;

  const tempArr = [];

  while (head !== null) {
    tempArr.push(head);
    head = head.next;
  }

  let i = 0;
  let j = tempArr.length - 1;

  while (i < j) {
    tempArr[i].next = tempArr[j];
    i++;

    //  For even
    if (i === j) break;

    tempArr[j].next = tempArr[i];
    j--;
  }

  //  Stop cycle
  tempArr[i].next = null;
};

:::

<hr/>

### 皮皮

:::spoiler Code

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """

        # Find the middle of the list
        // 1 2
        // 3 4
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the list
        // 1 2
        // 4 3
        prev = None
        current = slow.next
        while curr:
            temp = current.next
            current.next = prev
            prev = current
            current = temp
        slow.next = None 
        
        // 1 4 2 3
        second = prev
        first = head
        while second:
            temp1 = first.next
            temp2 = second.next

            first.next = second
            second.next = temp1

            first = temp1
            second = temp2
            

:::

<hr/>

### Howard

:::spoiler Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # time: O(N)
        # space: O(1)
        
        # 1. find middle node （if 偶數個 node，找前一個）
        slow = fast = h1 = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        
        # 2. reverse second-half of the linked list
        curr = slow.next
        h2 = self.reverse_list(curr)
        slow.next = None  # separate two linked list for step 3 (prevent circular)

        # 3. interleave 1st & 2nd half of linked list
        while h1 and h2:
            temp = h1.next
            h1.next = h2
            h1 = temp
            temp = h2.next
            h2.next = h1
            h2 = temp

    def reverse_list(self, head: ListNode) -> None:
        prev = None
        while head:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        return prev

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::