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;
    
    	    }
    	}
    
    }
    
  • // OJ: https://leetcode.com/problems/reorder-list/
    // Time: O(N)
    // Space: O(1)
    class Solution {
        int getLength(ListNode *head) {
            int ans = 0;
            for (; head; head = head->next) ++ans;
            return ans;
        }
        ListNode *splitList(ListNode *head) {
            int len = (getLength(head) - 1) / 2;
            while (len--) head = head->next;
            auto ans = head->next;
            head->next = nullptr;
            return ans;
        }
        ListNode *reverseList(ListNode *head) {
            ListNode dummy;
            while (head) {
                auto node = head;
                head = head->next;
                node->next = dummy.next;
                dummy.next = node;
            }
            return dummy.next;
        }
        void interleave(ListNode *first, ListNode *second) {
            while (second) {
                auto node = second;
                second = second->next;
                node->next = first->next;
                first->next = node;
                first = node->next;
            }
        }
    public:
        void reorderList(ListNode* head) {
            auto second = splitList(head);
            second = reverseList(second);
            interleave(head, second);
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
    
        def reverse(root):
          pre = None
          cur = root
          while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
          return pre
    
        if not head or not head.next:
          return
        slow = fast = head
        pre = None
        while fast and fast.next:
          pre = slow
          slow = slow.next
          fast = fast.next.next
        if pre:
          pre.next = None
        newHead = reverse(slow)
        ret = dummy = ListNode(-1)
        p1 = head
        p2 = newHead
        while p1 and p2:
          dummy.next = p1
          p1 = p1.next
          dummy = dummy.next
          dummy.next = p2
          p2 = p2.next
          dummy = dummy.next
    
        if p2:
          dummy.next = p2
        head.next = ret.next.next
    
    

All Problems

All Solutions