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