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:
- 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
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;
}
}
}