Java solution in 2 ms with comments


  • 0
    D
    public void reorderList(ListNode head) {
            if(head == null || head.next == null) return;
            ListNode pre = new ListNode(-1);
            pre.next = head;
            ListNode fast = head;
            ListNode slow = head;
            //split the list to two part
            while(fast != null && fast.next != null){
                pre = slow;
                fast = fast.next.next;
                slow = slow.next;
            }
    
            //reverse the right part
            ListNode right = pre.next.next;
            while(right != null){
                ListNode tempHead = pre.next;
                ListNode temp = right.next;
                pre.next = right;
                right.next = tempHead;
                right = temp;
            }
    
            //set left tail next is null
            ListNode leftTail = pre;
            ListNode rightHead = pre.next;
            leftTail.next = null;
            slow.next = null;
            ListNode leftHead = head;
    
            //insert right part into left part
            while(leftHead!=null){
                ListNode temp1 = leftHead.next;
                ListNode temp2 = rightHead.next;
                leftHead.next = rightHead;
                rightHead.next = temp1;
                pre = leftHead;
                leftHead = temp1;
                rightHead = temp2;
            }
            //if rightHead is not null, connect it to left tail
            if(rightHead != null) pre.next.next = rightHead;
        }

  • 0
    U
    This post is deleted!

Log in to reply
 

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