# 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:

L0 → L1 → … → Ln - 1 → Ln


Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 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 * 104].
• 1 <= Node.val <= 1000

# 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

• import java.util.Stack;

public class Reorder_List {

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {

ListNode dummy = new ListNode(0);

ListNode prev = dummy;
// 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
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;

p.next = rightReversed;
rightReversed.next = oldLeftNext;

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

}

public ListNode reverse (ListNode head) {

ListNode dummy = new ListNode(0);

ListNode current = dummy.next;

}

return dummy.next;
}
}

public class Solution_stack {

// @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);
ListNode prev = dummy;

// fast-slow pointers to find mid of list

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;

}
}

}

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

/**
* 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 {
return;
}
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;
}

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 ans = 0;
return ans;
}
int len = (getLength(head) - 1) / 2;
return ans;
}
ListNode dummy;
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:
second = reverseList(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:
"""
"""
return

# 快慢指针找到链表中点
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, pre 分别指向链表左右两半的第一个节点

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

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

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
"""

def reverse(root):
pre = None
cur = root
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre

return
pre = None
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
if pre:
pre.next = None
ret = dummy = ListNode(-1)
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


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return
}
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
}

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

• /**
* 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)
*     }
* }
*/

/**
*/
function reorderList(head: ListNode | null): void {

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 right = slow;
while (right.next != null) {
const next = left.next;
left.next = right;
right = right.next;
left.next.next = next;
left = left.next.next;
}
}


• /**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
*/
var reorderList = function (head) {
return;
}
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;
}

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


• /**
* 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 {
{
return;
}
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;
}

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 deque = VecDeque::new();
}
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;
}
}
}