Java solution: Reverse the second half and interleave two sublists


  • 0
    L
     public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode q = slow.next;
        slow.next = null;
        q = reverseList(q);
        interleave(head, q);
        return;
    }
    
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
    public void interleave(ListNode p, ListNode q) {
        ListNode pn = null;
        ListNode qn = null;
        while (q != null) {
            pn = p.next;
            qn = q.next;
            p.next = q;
            q.next = pn;
            q = qn;
            p = pn;
        }
        return;
    }

Log in to reply
 

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