143. Reorder list

143_solution1.c

#include "list_node.h"

void reorderList(struct ListNode *head) {
  if (!head || !head->next)
    return;

  // 1. find the end of the first half
  struct ListNode *slow = head, *fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }

  // 2. cut the list and reverse the second half
  struct ListNode *prev = NULL;
  struct ListNode *curr = slow->next;
  slow->next = NULL; // split into two lists

  while (curr) {
    struct ListNode *next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  struct ListNode *second = prev; // head of reversed second half

  // 3. merge: alternate nodes from first and second
  struct ListNode *first = head;
  while (second) {
    struct ListNode *next1 = first->next;
    struct ListNode *next2 = second->next;

    first->next = second;
    second->next = next1;

    first = next1;
    second = next2;
  }
}

143_solution2.c

#include <stdlib.h>

#include "list_node.h"

void reorderList(struct ListNode *head) {
  if (!head || !head->next)
    return;

  // 1. find the end of the first half
  struct ListNode *slow = head, *fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }

  // 2. cut the list and push the second half onto a stack
  int n = 0;
  for (struct ListNode *c = slow->next; c; c = c->next)
    n++;
  struct ListNode **stack = malloc(n * sizeof *stack);
  int top = 0;

  struct ListNode *curr = slow->next;
  slow->next = NULL; // split into two lists
  while (curr) {
    stack[top++] = curr;
    curr = curr->next;
  }

  // 3. merge: popping the stack yields the second half in reverse
  struct ListNode *first = head;
  while (top > 0) {
    struct ListNode *second = stack[--top];
    second->next = first->next;
    first->next = second;
    first = second->next;
  }
  free(stack);
}

143_solution3.c

#include <stdlib.h>

#include "list_node.h"

// array of node pointers used as a deque (front index l, back index r)
void reorderList(struct ListNode *head) {
  if (!head || !head->next)
    return;

  // 1. store every node
  int n = 0;
  for (struct ListNode *c = head; c; c = c->next)
    n++;
  struct ListNode **nodes = malloc(n * sizeof *nodes);
  struct ListNode *curr = head;
  for (int i = 0; i < n; i++, curr = curr->next)
    nodes[i] = curr;

  // 2. relink alternating between the front and the back
  int l = 0, r = n - 1;
  struct ListNode *tail = head; // nodes[0] is already the head
  l++;
  while (l <= r) {
    tail->next = nodes[r--];
    tail = tail->next;
    if (l <= r) {
      tail->next = nodes[l++];
      tail = tail->next;
    }
  }
  tail->next = NULL;
  free(nodes);
}

list_node.h

#pragma once

#include <stddef.h>

// Definition for singly-linked list.
struct ListNode {
  int val;
  struct ListNode *next;
};

143_solution1_split_and_reverse.cpp

#include "list_node.h"

class Solution {
public:
  void reorderList(ListNode *head) {
    if (!head || !head->next)
      return;

    // 1. find the end of the first half
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
      slow = slow->next;
      fast = fast->next->next;
    }

    // 2. cut the list
    ListNode *prev = nullptr;
    ListNode *curr = slow->next;
    slow->next = nullptr;

    // reverse the second half
    while (curr) {
      ListNode *next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }
    ListNode *second = prev; // head of reversed second half

    // 3. merge: alternate nodes from first and second
    ListNode *first = head;
    while (second) {
      ListNode *next1 = first->next;
      ListNode *next2 = second->next;

      first->next = second;
      second->next = next1;

      first = next1;
      second = next2;
    }
  }
};

143_solution2_stack.cpp

#include <stack>

#include "list_node.h"

class Solution {
public:
  void reorderList(ListNode *head) {
    if (!head || !head->next)
      return;

    // 1. find the end of the first half
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
      slow = slow->next;
      fast = fast->next->next;
    }

    // 2. cut the list and push the second half onto a stack
    std::stack<ListNode *> stack;
    for (ListNode *curr = slow->next; curr; curr = curr->next)
      stack.push(curr);
    slow->next = nullptr; // split into two lists

    // 3. merge: popping the stack yields the second half in reverse
    ListNode *first = head;
    while (!stack.empty()) {
      ListNode *second = stack.top();
      stack.pop();
      second->next = first->next;
      first->next = second;
      first = second->next;
    }
  }
};

143_solution3_deque.cpp

#include <deque>

#include "list_node.h"

class Solution {
public:
  void reorderList(ListNode *head) {
    if (!head || !head->next)
      return;

    // 1. store every node
    std::deque<ListNode *> deque;
    for (ListNode *curr = head; curr; curr = curr->next)
      deque.push_back(curr);

    // 2. relink alternating between the front and the back
    ListNode *tail = deque.front(); // the head stays first
    deque.pop_front();
    while (!deque.empty()) {
      tail->next = deque.back();
      deque.pop_back();
      tail = tail->next;
      if (!deque.empty()) {
        tail->next = deque.front();
        deque.pop_front();
        tail = tail->next;
      }
    }
    tail->next = nullptr;
  }
};

list_node.h

#pragma once

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

143_solution1.go

package linkedlists

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // 1. find the end of the first half
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 2. cut the list and reverse the second half
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil // split into two lists

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    second := prev // head of reversed second half

    // 3. merge: alternate nodes from first and second
    first := head
    for second != nil {
        next1, next2 := first.Next, second.Next

        first.Next = second
        second.Next = next1

        first, second = next1, next2
    }
}

143_solution2.go

package linkedlists

func reorderListStack(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // 1. find the end of the first half
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 2. cut the list and push the second half onto a stack
    var stack []*ListNode
    for curr := slow.Next; curr != nil; curr = curr.Next {
        stack = append(stack, curr)
    }
    slow.Next = nil // split into two lists

    // 3. merge: popping the stack yields the second half in reverse
    first := head
    for len(stack) > 0 {
        second := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        second.Next = first.Next
        first.Next = second
        first = second.Next
    }
}

143_solution3.go

package linkedlists

// slice of node pointers used as a deque (front index l, back index r)
func reorderListDeque(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // 1. store every node
    var nodes []*ListNode
    for curr := head; curr != nil; curr = curr.Next {
        nodes = append(nodes, curr)
    }

    // 2. relink alternating between the front and the back
    l, r := 1, len(nodes)-1
    tail := head // nodes[0] is already the head
    for l <= r {
        tail.Next = nodes[r]
        tail = tail.Next
        r--
        if l <= r {
            tail.Next = nodes[l]
            tail = tail.Next
            l++
        }
    }
    tail.Next = nil
}

list_node.go

package linkedlists

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

143_solution1.java

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;

        // 1. find the end of the first half
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. cut the list and reverse the second half
        ListNode prev = null;
        ListNode curr = slow.next;
        slow.next = null; // split into two lists

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        ListNode second = prev; // head of reversed second half

        // 3. merge: alternate nodes from first and second
        ListNode first = head;
        while (second != null) {
            ListNode next1 = first.next;
            ListNode next2 = second.next;

            first.next = second;
            second.next = next1;

            first = next1;
            second = next2;
        }
    }
}

143_solution2.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;

        // 1. find the end of the first half
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. cut the list and push the second half onto a stack
        Deque<ListNode> stack = new ArrayDeque<>();
        for (ListNode curr = slow.next; curr != null; curr = curr.next)
            stack.push(curr);
        slow.next = null; // split into two lists

        // 3. merge: popping the stack yields the second half in reverse
        ListNode first = head;
        while (!stack.isEmpty()) {
            ListNode second = stack.pop();
            second.next = first.next;
            first.next = second;
            first = second.next;
        }
    }
}

143_solution3.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;

        // 1. store every node
        Deque<ListNode> deque = new ArrayDeque<>();
        for (ListNode curr = head; curr != null; curr = curr.next)
            deque.addLast(curr);

        // 2. relink alternating between the front and the back
        ListNode tail = deque.pollFirst(); // the head stays first
        while (!deque.isEmpty()) {
            tail.next = deque.pollLast();
            tail = tail.next;
            if (!deque.isEmpty()) {
                tail.next = deque.pollFirst();
                tail = tail.next;
            }
        }
        tail.next = null;
    }
}

ListNode.java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

143_solution1.js

const ListNode = require("./list_node");

var reorderList = function (head) {
  if (!head || !head.next) return;

  // 1. find the end of the first half
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. cut the list and reverse the second half
  let prev = null;
  let curr = slow.next;
  slow.next = null; // split into two lists

  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  let second = prev; // head of reversed second half

  // 3. merge: alternate nodes from first and second
  let first = head;
  while (second) {
    const next1 = first.next;
    const next2 = second.next;

    first.next = second;
    second.next = next1;

    first = next1;
    second = next2;
  }
};

143_solution2.js

const ListNode = require("./list_node");

var reorderList = function (head) {
  if (!head || !head.next) return;

  // 1. find the end of the first half
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. cut the list and push the second half onto a stack
  const stack = [];
  for (let curr = slow.next; curr; curr = curr.next) stack.push(curr);
  slow.next = null; // split into two lists

  // 3. merge: popping the stack yields the second half in reverse
  let first = head;
  while (stack.length) {
    const second = stack.pop();
    second.next = first.next;
    first.next = second;
    first = second.next;
  }
};

143_solution3.js

const ListNode = require("./list_node");

// array used as a deque via front/back indices (shift() would be O(n))
var reorderList = function (head) {
  if (!head || !head.next) return;

  // 1. store every node
  const nodes = [];
  for (let curr = head; curr; curr = curr.next) nodes.push(curr);

  // 2. relink alternating between the front and the back
  let l = 1;
  let r = nodes.length - 1;
  let tail = head; // nodes[0] is already the head
  while (l <= r) {
    tail.next = nodes[r--];
    tail = tail.next;
    if (l <= r) {
      tail.next = nodes[l++];
      tail = tail.next;
    }
  }
  tail.next = null;
};

list_node.js

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

module.exports = ListNode;

143_solution1.py

from typing import Optional

from list_node import ListNode


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        # 1. find the end of the first half
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. cut the list and reverse the second half
        prev = None
        curr = slow.next
        slow.next = None  # split into two lists

        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        second = prev  # head of reversed second half

        # 3. merge: alternate nodes from first and second
        first = head
        while second:
            next1, next2 = first.next, second.next

            first.next = second
            second.next = next1

            first, second = next1, next2

143_solution2.py

from typing import Optional

from list_node import ListNode


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        # 1. find the end of the first half
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. cut the list and push the second half onto a stack
        stack = []
        curr = slow.next
        while curr:
            stack.append(curr)
            curr = curr.next
        slow.next = None  # split into two lists

        # 3. merge: popping the stack yields the second half in reverse
        first = head
        while stack:
            second = stack.pop()
            second.next = first.next
            first.next = second
            first = second.next

143_solution3.py

from collections import deque
from typing import Optional

from list_node import ListNode


class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        # 1. store every node
        nodes = deque()
        curr = head
        while curr:
            nodes.append(curr)
            curr = curr.next

        # 2. relink alternating between the front and the back
        tail = nodes.popleft()  # the head stays first
        while nodes:
            tail.next = nodes.pop()
            tail = tail.next
            if nodes:
                tail.next = nodes.popleft()
                tail = tail.next
        tail.next = None

list_node.py

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

143_solution1.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
        // 1. count the nodes to find the end of the first half
        // (no slow/fast pointers: the borrow checker forbids aliasing)
        let mut len = 0;
        let mut cur = head.as_ref();
        while let Some(node) = cur {
            len += 1;
            cur = node.next.as_ref();
        }
        if len < 3 {
            return;
        }

        let mut mid = head.as_mut().unwrap();
        for _ in 0..(len - 1) / 2 {
            mid = mid.next.as_mut().unwrap();
        }

        // 2. cut the list and reverse the second half
        let mut curr = mid.next.take(); // split into two lists
        let mut second = None;
        while let Some(mut node) = curr {
            curr = node.next.take();
            node.next = second;
            second = Some(node);
        }

        // 3. merge: alternate nodes from first and second
        let mut first = head.as_mut();
        while let (Some(node), Some(mut s)) = (first, second.take()) {
            second = s.next.take();
            s.next = node.next.take();
            node.next = Some(s);
            first = node.next.as_mut().unwrap().next.as_mut();
        }
    }
}

143_solution2.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
        // 1. count the nodes to find the end of the first half
        let mut len = 0;
        let mut cur = head.as_ref();
        while let Some(node) = cur {
            len += 1;
            cur = node.next.as_ref();
        }
        if len < 3 {
            return;
        }

        let mut mid = head.as_mut().unwrap();
        for _ in 0..(len - 1) / 2 {
            mid = mid.next.as_mut().unwrap();
        }

        // 2. cut the list and push the second half onto a stack
        let mut stack = Vec::new();
        let mut curr = mid.next.take(); // split into two lists
        while let Some(mut node) = curr {
            curr = node.next.take();
            stack.push(node);
        }

        // 3. merge: popping the stack yields the second half in reverse
        let mut first = head.as_mut();
        while let (Some(node), Some(mut s)) = (first, stack.pop()) {
            s.next = node.next.take();
            node.next = Some(s);
            first = node.next.as_mut().unwrap().next.as_mut();
        }
    }
}

143_solution3.rs

use std::collections::VecDeque;

use crate::list_node::ListNode;

impl Solution {
    pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
        // 1. detach every node into a deque
        let mut deque = VecDeque::new();
        let mut curr = head.take();
        while let Some(mut node) = curr {
            curr = node.next.take();
            deque.push_back(node);
        }

        // 2. relink alternating between the front and the back
        let mut tail = head;
        let mut from_front = true;
        loop {
            let node = if from_front {
                deque.pop_front()
            } else {
                deque.pop_back()
            };
            let Some(node) = node else { break };
            from_front = !from_front;

            *tail = Some(node);
            tail = &mut tail.as_mut().unwrap().next;
        }
    }
}

list_node.rs

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}