143 Reorder List – Medium¶

Problem:¶

Given a singly linked list L: 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}.

Thoughts¶

This problem can be easily solved by using HashMap, but due to the requirement, “do this in-place”. So the plan is to complete in three steps. 1 Find the middle element of the list. 2 Do a reverse operation on the second half of the list. 3 Merge the first half and second half in a fashion that picks element from each in order.

Solutions:¶

/**
 * 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;
        }
        ListNode mid = findMid(head);
        ListNode head2 = reverse(mid.next);
        mid.next = null;
        merge(head, head2);
    }
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode fakeHead = new ListNode(-1);
        ListNode node = fakeHead;
        while (head1 != null && head2 != null) {
            node.next = head1;
            head1 = head1.next;
            node.next.next = head2;
            head2 = head2.next;
            node = node.next.next;
        }
        if (head1 != null) {
            node.next = head1;
        }
        if (head2 != null) {
            node.next = head2;
        }
        return fakeHead.next;
    }
    private ListNode reverse(ListNode head) {
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode node = head;
        ListNode next = null;
        while(node != null) {
            next = node.next;
            node.next = fakeHead.next;
            fakeHead.next = node;
            node = next;
        }
        head.next = null;
        return fakeHead.next;
    }
    private ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}