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



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

/**
* 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 . 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: , 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;

}
}

}

• // 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(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