A C# O(N) 180ms Solution by Reversing List


  • 0
    L
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return;
        ListNode pre = head, head2 = head, head1 = head,tmpHead2 = null;
        int count = 0;
        for (ListNode tmp = head; tmp != null; tmp = tmp.next, count++) ;
        count = (count + 1) >> 1;
        for (; count > 0; pre = pre == head2 ? pre : pre.next, head2 = pre.next, count--);
        for(pre.next = null; head2 != null;){ //Reverse List
            pre = head2.next;
            head2.next = tmpHead2;
            tmpHead2 = head2;
            head2 = pre;
        }
        for(head2 = tmpHead2; head2 != null; ){
            pre = head2.next;
            head2.next = head1.next;
            head1.next = head2;
            head1 = head2.next;
            head2 = pre;
        }
    }

  • 0
    L
    //Below is another Accepted solution without reversing list. Time O((N/2)2), In Place
    
    public void ReorderList2(ListNode head)
    {
        if (head == null || head.next == null || head.next.next == null) return;
        int count = 0;
        for (ListNode tmp = head; tmp != null; tmp = tmp.next, count++) ;
        count = (count + 1) >> 1;
        ListNode pre = head, head2 = head, head1 = head;
        for (int i = count; i > 0; pre = pre == head2 ? pre : pre.next, head2 = pre.next, i--) ;
        pre.next = null;
        while (true)
        {
            ListNode cur;
            for (cur = head2, pre = head2; cur.next != null; pre = pre == cur ? pre : pre.next, cur = pre.next) ;
            pre.next = null;
            cur.next = head1.next;
            head1.next = cur;
            head1 = cur.next;
            if (cur == head2) break;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.