AC Java Solution


  • 0
    D
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void reorderList(ListNode head) {
           if (head == null || head.next == null) {    
                return;    
            }
            // Find the the mid point of this linked-list
            ListNode fast= head;
            ListNode slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            // Split the linked-list
            ListNode second = slow.next;
            slow.next = null;
            // reverse the second half
            ListNode prev = null;
            while (second != null) {
                ListNode next = second.next;
                second.next = prev;
                prev = second;
                second = next;
            }
            // Final phase: Combining two halves
            ListNode l1 = head;
            ListNode l2 = prev;
            while (l1 != null && l2 != null) {
                ListNode l1next = l1.next;
                ListNode l2next = l2.next;
                l1.next = l2;
                l2.next = l1next;
                l1 = l1next;
                l2 = l2next;
            }
       
        }    
    }

Log in to reply
 

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