_143. Reorder List.md

143. Reorder List

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 11, 2024

Last updated : July 01, 2024

---

Related Topics : Linked List, Two Pointers, Stack, Recursion

Acceptance Rate : 60.97 %

---

Solutions

• m143 v2 reverse.java
• m143.py

Java

m143 v2 reverse.java

/**
 * 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) {
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode prev = slow;
        slow = slow.next;
        prev.next = null;
        while (slow != null) {
            ListNode temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;
        }

        ListNode front = head.next;
        ListNode back = prev;
        ListNode newHead = head;

        while (front != null && back != null) {
            if (back != null) {
                newHead.next = back;
                back = back.next;
                newHead = newHead.next;
            }

            if (front != null) {
                newHead.next = front;
                front = front.next;
                newHead = newHead.next;
            }
        }
        if (back != null) {
            newHead.next = back;
            back.next = null;
        }
    }
}

Python

m143.py

# 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: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        toReadd = []

        curr = head
        while curr :
            toReadd.append(curr)
            curr = curr.next

        curr = head
        numNodes = len(toReadd)
        last = head
        while numNodes > 1 :
            toReadd[-1].next = curr.next
            curr.next = toReadd.pop()
            last = curr.next
            curr = curr.next.next
            numNodes -= 2

        if numNodes == 0 :
            last.next = None
        else :
            last.next = toReadd.pop()
            last.next.next = None