PattySung

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4] Output: [1,4,2,3] Example 2:

Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]

<解題>


class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null ) return ;

        ListNode slow = head;
        ListNode fast = head;
        ListNode temp = null;

        while(fast!= null && fast.next != null){
            temp = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        temp.next = null;
        
        ListNode l2 = reverse(slow);
        merge(head, l2);
    }

    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    private void merge(ListNode l1, ListNode l2){
        while(true){
            ListNode n1 = l1.next;
            ListNode n2 = l2.next;
            l1.next = l2;
            if(n1 == null) return;
            l2.next = n1;
            l1 = n1;
            l2 = n2;
        }
        
    }
}

Time Complexity: Space Complexity:

Leetcode-143. Reorder List

<解題>