Easy to understand Java solution


  • 0
    L
    public class Solution {
        public void reorderList(ListNode head) {
            if(head == null || head.next == null) return;
            ListNode mid = findMid(head);
            ListNode high = reverse(mid.next);
            mid.next = null;
            ListNode low = head;
            ListNode fake = new ListNode(0);
            ListNode cur = fake;
            while(high != null) {
                cur.next = low;
                low = low.next;
                cur.next.next = high;
                high = high.next;
                cur = cur.next.next;
            }
            if(low != null) cur.next = low;
            head = fake.next;
        }
        private ListNode findMid(ListNode head) {
            if(head == null) return null;
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
        public ListNode reverse(ListNode head) {
            ListNode prev = null;
            ListNode next = null;
            while(head != null){
                next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
    }
    

    Notice after findMid & reverse, the last element of low sub-list should point to nowhere.


Log in to reply
 

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