Share my simple Java implementation


  • 0
    M
    /*
        1. reverse the second half
        2. merge the second half into the first half
    */ 
    public class Solution {
        public void reorderList(ListNode head) {
            if (head == null || head.next == null) {
                return;
            } 
            ListNode slow = head, fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode prev = null, cur = slow.next;
            slow.next = null;  // break the first half apart from the linked list
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            for (ListNode p = head, q = prev; q != null; ) {
                ListNode qNext = q.next;
                q.next = p.next;
                p.next = q;
                p = p.next.next;
                q = qNext;
            }
        }
    }

Log in to reply
 

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