Question

Formatted question description: https://leetcode.ca/all/143.html

143	Reorder List

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.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.


@tag-linkedlist

Algorithm

Divided into the following three small questions:

1. Use the fast/slow pointers to find the midpoint of the linked list and disconnect the linked list from the midpoint to form two independent linked lists.
2. Reverse the second half of list.
3. Insert the elements of the second half linked list into the first linked list.

Code

Java

import java.util.Stack;

public class Reorder_List {


	/**
	 * 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 dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;
            ListNode fast = head, slow = head;
            // step-1, find mid
            while (fast != null && fast.next != null) {
                fast = fast.next.next;

                prev = slow;
                slow = slow.next;
            }

            // 1,2,3  prev->1, slow->2
            // 1,2,3,4  prev->2, slow->3
            // that is, left is always smaller or equal to right

            ListNode right = prev.next; // not using slow, because for case list [1]. update: no, must tive single node special check
            prev.next = null; // @note:@memorize: cut

            // step-2, reverse 2nd half
            ListNode rightReversed = reverse(right);

            // step-3, merge
            ListNode p = head;
            while (p != null || rightReversed != null) {

                if (p.next == null) { // left: [1], right [2,3], directly append
                    p.next = rightReversed;
                    break;
                }

                else {

                    // record second of both left/right list
                    ListNode oldLeftNext = p.next;
                    // p.next = new ListNode(rightReversed.val);// this is one way, but not in place...
                    // p.next.next = oldLeftNext;

                    ListNode oldRightNext = rightReversed.next;

                    // linked two heads from left and right
                    p.next = rightReversed;
                    rightReversed.next = oldLeftNext;

                    // update
                    p = oldLeftNext;
                    rightReversed = oldRightNext;
                }
            }

            head = dummy.next;
        }

        public ListNode reverse (ListNode head) {

            ListNode dummy = new ListNode(0);
            dummy.next = head;


            while (head.next != null) {
                ListNode newhead = head.next;
                ListNode current = dummy.next;

                dummy.next = newhead;
                head.next = newhead.next;
                newhead.next = current;
            }

            return dummy.next;
        }
    }


	public class Solution_stack {
	    public void reorderList(ListNode head) {

	        // @note: my idea is, find mid point, then 2nd half put in a stack to reverse the order I get the 2nd half nodes
	        // eg: [1,2,3,4], in stack is 4->3, then 1, sk.pop=4, 2, sk.pop=3
	        if (head == null || head.next == null || head.next.next == null) { // if single node list, then return
	            return;
	        }

	        ListNode dummy = new ListNode(0);
	        dummy.next = head;
	        ListNode prev = dummy;

	        // fast-slow pointers to find mid of list
	        ListNode fast = head;
	        ListNode slow = head;

	        while (fast != null && fast.next != null) { // no need check slow, since fast is reaching end first

	            prev = slow;
	            slow = slow.next;
	            fast = fast.next.next;
	        }

	        // now slow is at mid, prev at mid-1
	        // from mid to end, push to stack
	        Stack<ListNode> sk = new Stack<>();

	        ListNode mid = slow;
	        while (slow != null) {
	            sk.push(slow);
	            // System.out.println("push to stack: " + slow.val);
	            slow = slow.next;
	        }

	        // start reorder
	        ListNode tail = head; // @note: if only one node as head, then head is in stack
	        while (!sk.isEmpty() && tail != mid) { // @note: if tail is already mid node, then done
	            ListNode originalNext = tail.next;
	            tail.next = sk.pop();
	            tail = tail.next; // now tail is the one from 2nd half

	            if (tail == mid) {
	                break;
	            }

	            tail.next = originalNext;
	            tail = tail.next; // now tail is next of left-half current node
	        }

	        // @note:@memorize: very important, avoid infinite self-looping
	        tail.next = null;

	        return;

	    }
	}

}

All Problems

All Solutions