Question

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

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

L₀ → L₁ → … → L_{n - 1} → L_n

Reorder the list to be on the following form:

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 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]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10⁴].
1 <= Node.val <= 1000

Algorithm

Divided into the following three small questions:

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.
Reverse the second half of list.
Insert the elements of the second half linked list into the first linked list.

Code

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;

	    }
	}

}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode cur = slow.next;
        slow.next = null;

        ListNode pre = null;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        cur = head;

        while (pre != null) {
            ListNode t = pre.next;
            pre.next = cur.next;
            cur.next = pre;
            cur = pre.next;
            pre = t;
        }
    }
}

// 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:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None or head.next is None:
            return

        # 快慢指针找到链表中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next

        # cur 指向右半部分链表
        cur = slow.next
        slow.next = None

        # 反转右半部分链表
        pre = None
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        cur = head
        # 此时 cur, pre 分别指向链表左右两半的第一个节点

        while pre:
            t = pre.next
            pre.next = cur.next
            cur.next = pre
            cur, pre = pre.next, t

############

# 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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
    }

    cur := slow.Next
    slow.Next = nil

    var pre *ListNode
    for cur != nil {
        t := cur.Next
        cur.Next = pre
        pre, cur = cur, t
    }
    cur = head

    for pre != nil {
        t := pre.Next
        pre.Next = cur.Next
        cur.Next = pre
        cur, pre = pre.Next, t
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

/**
 Do not return anything, modify head in-place instead.
 */
function reorderList(head: ListNode | null): void {
    let slow = head;
    let fast = head;

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

    let next = slow.next;
    slow.next = null;
    while (next != null) {
        [next.next, slow, next] = [slow, next, next.next];
    }

    let left = head;
    let right = slow;
    while (right.next != null) {
        const next = left.next;
        left.next = right;
        right = right.next;
        left.next.next = next;
        left = left.next.next;
    }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
    if (!head || !head.next) {
        return;
    }
    let slow = head;
    let fast = head.next;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let cur = slow.next;
    slow.next = null;

    let pre = null;
    while (cur) {
        const t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    cur = head;

    while (pre) {
        const t = pre.next;
        pre.next = cur.next;
        cur.next = pre;
        cur = pre.next;
        pre = t;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null)
        {
            return;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode cur = slow.next;
        slow.next = null;

        ListNode pre = null;
        while (cur != null)
        {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        cur = head;

        while (pre != null)
        {
            ListNode t = pre.next;
            pre.next = cur.next;
            cur.next = pre;
            cur = pre.next;
            pre = t;
        }
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
use std::collections::VecDeque;
impl Solution {
    pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
        let mut tail = &mut head.as_mut().unwrap().next;
        let mut head = tail.take();
        let mut deque = VecDeque::new();
        while head.is_some() {
            let next = head.as_mut().unwrap().next.take();
            deque.push_back(head);
            head = next;
        }
        let mut flag = false;
        while !deque.is_empty() {
            *tail = if flag {
                deque.pop_front().unwrap()
            } else {
                deque.pop_back().unwrap()
            };
            tail = &mut tail.as_mut().unwrap().next;
            flag = !flag;
        }
    }
}

143 - Reorder List

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions