143 Reorder List

143. Reorder List

1. Question

Given a singly linked listL:L0→L1→…→Ln-1→Ln, reorder it to:L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example, Given{1,2,3,4}, reorder it to{1,4,2,3}.

2. Implementation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode fast = head, slow = head;

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

        ListNode p2 = slow.next;
        slow.next = null;

        p2 = reverse(p2);
        ListNode p1 = head;

        while (p1 != null && p2 != null) {
            ListNode nextNode = p2.next;
            p2.next = p1.next;
            p1.next = p2;
            p2 = nextNode;
            p1 = p1.next.next;
        }
    }

    public ListNode reverse(ListNode head) {
        ListNode preNode = null, nextNode = null;
        ListNode curNode = head;

        while (curNode != null) {
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }
}

3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(1)