Leetcode 143. Reorder List (v hard)

https://leetcode.com/problems/reorder-list/description/

initial

So my initial attempt was placing head first, update head to the right, then add the node which next is None (i.e. the tail) then making that node which next is None as None too.

But it goes on infinite loop

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        ans = ListNode(0)
        cur = ans
        while True:
            if not head.next:
                break
            cur.next = head
            head = head.next
            tmp = head
            while tmp.next !=None:
                tmp = tmp.next
            cur = cur.next
            cur.next = tmp
            tmp=None
            cur = cur.next
        print(ans)

solution

so theres 3 concepts here

1) finding middle node
2) reversing the second half (with slow=slow.next cuz slow is middle point, slow.next= head of second half)
3) merge those halves together

class Solution {
    public void reorderList(ListNode head) {
        if(head==null)return;

//        find middle node
        ListNode slow = head; ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast = fast.next.next;
        }
        //reverse the right half
        ListNode prev = null;
        // v impt slow is the middle of the node, we want the head of the second half so we do slow.next (applies for both odd and even lengths)
        ListNode cur = slow.next;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next=prev;
            prev=cur;
            cur=tmp;
        }
        slow.next=null;

        ListNode first = head;
        ListNode second = prev;
        while(second!=null){
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;
            first.next=second;
            second.next=temp1;

            first=temp1;
            second=temp2;
        }
    }
}

complexity

n time