Linked-list problems are pointer puzzles: almost every classic one is solved by two pointers moving at different speeds or distances, by reversing links in place, or by re-wiring nodes without allocating. This topic collects the problems interviewers actually ask and the handful of techniques that solve them.
head
↓
┌────┬───┐ ┌────┬───┐ ┌────┬───┐ ┌────┬───┐
│ 10 │ ●─┼──▶│ 20 │ ●─┼──▶│ 30 │ ●─┼──▶│ 40 │ ∅ │
└────┴───┘ └────┴───┘ └────┴───┘ └────┴───┘
data nextRecap: what costs what
| Operation | Singly linked list | Dynamic array |
|---|---|---|
Access i-th element | O(n) — walk from head | O(1) |
| Insert / delete at head | O(1) | O(n) — shift everything |
| Insert / delete after a known node | O(1) — re-wire two links | O(n) |
| Insert / delete at tail | O(n) (O(1) with a tail pointer) | amortised O(1) |
| Search | O(n) | O(n) (O(log n) if sorted) |
| Memory per element | value + one pointer, scattered | value only, contiguous and cache-friendly |
The problems in this topic exploit the one thing a list does better than an array: moving a node costs O(1) and no allocation. Reversing, merging, swapping pairs and segregating are all done by changing next pointers, never by copying values into a new container.
The techniques behind every problem
Node and helpers used in every solution
Every program below carries the same three pieces: a Node, build(values) that turns an array into a list, and toStr(head) that prints a list as space-separated values. They are the only boilerplate — the solutions themselves are the functions in between.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values): # [1, 2, 3] → 1 → 2 → 3
head = None
for v in reversed(values): # prepend from the back, so order is kept
node = Node(v)
node.next = head
head = node
return head
def to_str(head): # "1 2 3"
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def length(head):
n = 0
while head:
n += 1
head = head.next
return n
head = build([10, 20, 30, 40, 50])
print(to_str(head))
print("length:", length(head))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) { // {1, 2, 3} → 1 → 2 → 3
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) { // prepend from the back
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) { // "1 2 3"
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
int length(Node* head) {
int n = 0;
for (Node* c = head; c; c = c->next) n++;
return n;
}
int main() {
Node* head = build({10, 20, 30, 40, 50});
cout << toStr(head) << "\n";
cout << "length: " << length(head) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) { // {1, 2, 3} → 1 → 2 → 3
Node head = null;
for (int i = v.length - 1; i >= 0; i--) { // prepend from the back
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) { // "1 2 3"
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static int length(Node head) {
int n = 0;
for (Node c = head; c != null; c = c.next) n++;
return n;
}
public static void main(String[] args) {
Node head = build(new int[]{10, 20, 30, 40, 50});
System.out.println(toStr(head));
System.out.println("length: " + length(head));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) { // [1, 2, 3] → 1 → 2 → 3
let head = null;
for (let i = values.length - 1; i >= 0; i--) { // prepend from the back
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) { // "1 2 3"
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function length(head) {
let n = 0;
for (let c = head; c; c = c.next) n++;
return n;
}
const head = build([10, 20, 30, 40, 50]);
console.log(toStr(head));
console.log("length:", length(head));10 20 30 40 50
length: 5Middle of a linked list
step 0: slow fast
↓ ↓
10 → 20 → 30 → 40 → 50
step 1: slow fast
step 2: slow fast = ∅ → stop, slow = 30class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def middle(head):
slow = fast = head
while fast and fast.next: # fast moves 2, slow moves 1
slow = slow.next
fast = fast.next.next
return slow
for values in ([10, 20, 30, 40, 50], [10, 20, 30, 40]):
head = build(values)
print(to_str(head), "→ middle", middle(head).data)#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* middle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) { // fast moves 2, slow moves 1
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
int main() {
for (vector<int> values : {vector<int>{10, 20, 30, 40, 50}, vector<int>{10, 20, 30, 40}}) {
Node* head = build(values);
cout << toStr(head) << " → middle " << middle(head)->data << "\n";
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node middle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) { // fast moves 2, slow moves 1
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static void main(String[] args) {
for (int[] values : new int[][]{{10, 20, 30, 40, 50}, {10, 20, 30, 40}}) {
Node head = build(values);
System.out.println(toStr(head) + " → middle " + middle(head).data);
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function middle(head) {
let slow = head, fast = head;
while (fast && fast.next) { // fast moves 2, slow moves 1
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
for (const values of [[10, 20, 30, 40, 50], [10, 20, 30, 40]]) {
const head = build(values);
console.log(toStr(head), "→ middle", middle(head).data);
}10 20 30 40 50 → middle 30
10 20 30 40 → middle 30Time O(n) · Space O(1)
Nth node from the end
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def nth_from_end(head, n):
first = head
for _ in range(n): # move first n nodes ahead
if first is None:
return None # n is larger than the length
first = first.next
second = head
while first: # now move both; the gap stays n
first = first.next
second = second.next
return second
head = build([10, 20, 30, 40, 50])
for n in (1, 2, 5, 6):
node = nth_from_end(head, n)
print("n =", n, "→", node.data if node else "none")#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
Node* nthFromEnd(Node* head, int n) {
Node* first = head;
for (int i = 0; i < n; i++) { // move first n nodes ahead
if (!first) return nullptr; // n is larger than the length
first = first->next;
}
Node* second = head;
while (first) { // now move both; the gap stays n
first = first->next;
second = second->next;
}
return second;
}
int main() {
Node* head = build({10, 20, 30, 40, 50});
for (int n : {1, 2, 5, 6}) {
Node* node = nthFromEnd(head, n);
cout << "n = " << n << " → " << (node ? to_string(node->data) : "none") << "\n";
}
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static Node nthFromEnd(Node head, int n) {
Node first = head;
for (int i = 0; i < n; i++) { // move first n nodes ahead
if (first == null) return null; // n is larger than the length
first = first.next;
}
Node second = head;
while (first != null) { // now move both; the gap stays n
first = first.next;
second = second.next;
}
return second;
}
public static void main(String[] args) {
Node head = build(new int[]{10, 20, 30, 40, 50});
for (int n : new int[]{1, 2, 5, 6}) {
Node node = nthFromEnd(head, n);
System.out.println("n = " + n + " → " + (node != null ? String.valueOf(node.data) : "none"));
}
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function nthFromEnd(head, n) {
let first = head;
for (let i = 0; i < n; i++) { // move first n nodes ahead
if (!first) return null; // n is larger than the length
first = first.next;
}
let second = head;
while (first) { // now move both; the gap stays n
first = first.next;
second = second.next;
}
return second;
}
const head = build([10, 20, 30, 40, 50]);
for (const n of [1, 2, 5, 6]) {
const node = nthFromEnd(head, n);
console.log("n =", n, "→", node ? node.data : "none");
}n = 1 → 50
n = 2 → 40
n = 5 → 10
n = 6 → noneTime O(n) · Space O(1)
Reverse a linked list
before: prev curr next
∅ ← 10 → 20 → 30 → 40 → 50
flip: ∅ ← 10 20 → 30 → 40 → 50 curr.next = prev
advance: prev curr next
∅ ← 10 20 → 30 → 40 → 50 prev = curr, curr = nextclass Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def reverse_iter(head):
prev, curr = None, head
while curr:
nxt = curr.next # save the rest of the list
curr.next = prev # flip the link
prev, curr = curr, nxt # advance both pointers
return prev # prev is the new head
def reverse_rec(head):
if head is None or head.next is None:
return head # empty or single node: already reversed
rest = reverse_rec(head.next) # reverse everything after head
head.next.next = head # old second node now points back at head
head.next = None # head becomes the tail
return rest
head = build([10, 20, 30, 40, 50])
head = reverse_iter(head)
print("iterative:", to_str(head))
head = reverse_rec(head) # reverse it back
print("recursive:", to_str(head))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* reverseIter(Node* head) {
Node* prev = nullptr;
Node* curr = head;
while (curr) {
Node* next = curr->next; // save the rest of the list
curr->next = prev; // flip the link
prev = curr; // advance both pointers
curr = next;
}
return prev; // prev is the new head
}
Node* reverseRec(Node* head) {
if (!head || !head->next) return head; // empty or single node
Node* rest = reverseRec(head->next); // reverse everything after head
head->next->next = head; // old second node points back at head
head->next = nullptr; // head becomes the tail
return rest;
}
int main() {
Node* head = build({10, 20, 30, 40, 50});
head = reverseIter(head);
cout << "iterative: " << toStr(head) << "\n";
head = reverseRec(head); // reverse it back
cout << "recursive: " << toStr(head) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node reverseIter(Node head) {
Node prev = null, curr = head;
while (curr != null) {
Node next = curr.next; // save the rest of the list
curr.next = prev; // flip the link
prev = curr; // advance both pointers
curr = next;
}
return prev; // prev is the new head
}
static Node reverseRec(Node head) {
if (head == null || head.next == null) return head; // empty or single node
Node rest = reverseRec(head.next); // reverse everything after head
head.next.next = head; // old second node points back at head
head.next = null; // head becomes the tail
return rest;
}
public static void main(String[] args) {
Node head = build(new int[]{10, 20, 30, 40, 50});
head = reverseIter(head);
System.out.println("iterative: " + toStr(head));
head = reverseRec(head); // reverse it back
System.out.println("recursive: " + toStr(head));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function reverseIter(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next; // save the rest of the list
curr.next = prev; // flip the link
prev = curr; // advance both pointers
curr = next;
}
return prev; // prev is the new head
}
function reverseRec(head) {
if (!head || !head.next) return head; // empty or single node
const rest = reverseRec(head.next); // reverse everything after head
head.next.next = head; // old second node points back at head
head.next = null; // head becomes the tail
return rest;
}
let head = build([10, 20, 30, 40, 50]);
head = reverseIter(head);
console.log("iterative:", toStr(head));
head = reverseRec(head); // reverse it back
console.log("recursive:", toStr(head));iterative: 50 40 30 20 10
recursive: 10 20 30 40 50Time O(n) · Space O(1) iterative · O(n) recursive (call stack)
Reverse a linked list in groups of k
10 → 20 → 30 │ 40 → 50 → 60 groups of k = 3
reverse group 1: 30 → 20 → 10 → ? 10 was the head, now the tail
reverse group 2: 60 → 50 → 40
link: 30 → 20 → 10 → 60 → 50 → 40Recursive — the natural way to express “reverse this group, then link to the reversed rest”:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def reverse_k_rec(head, k):
curr, prev = head, None
count = 0
while curr and count < k: # reverse the first k nodes
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
count += 1
if curr: # more nodes left: reverse them and link
head.next = reverse_k_rec(curr, k) # head is now the tail of this group
return prev # prev is the new head of this group
for values in ([10, 20, 30, 40, 50, 60], [10, 20, 30, 40, 50]):
print(to_str(reverse_k_rec(build(values), 3)))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* reverseKRec(Node* head, int k) {
Node* curr = head;
Node* prev = nullptr;
int count = 0;
while (curr && count < k) { // reverse the first k nodes
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (curr) // more nodes left: reverse them and link
head->next = reverseKRec(curr, k); // head is now the tail of this group
return prev; // prev is the new head of this group
}
int main() {
for (vector<int> values : {vector<int>{10, 20, 30, 40, 50, 60}, vector<int>{10, 20, 30, 40, 50}})
cout << toStr(reverseKRec(build(values), 3)) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node reverseKRec(Node head, int k) {
Node curr = head, prev = null;
int count = 0;
while (curr != null && count < k) { // reverse the first k nodes
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (curr != null) // more nodes left: reverse them and link
head.next = reverseKRec(curr, k); // head is now the tail of this group
return prev; // prev is the new head of this group
}
public static void main(String[] args) {
for (int[] values : new int[][]{{10, 20, 30, 40, 50, 60}, {10, 20, 30, 40, 50}})
System.out.println(toStr(reverseKRec(build(values), 3)));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function reverseKRec(head, k) {
let curr = head, prev = null, count = 0;
while (curr && count < k) { // reverse the first k nodes
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (curr) // more nodes left: reverse them and link
head.next = reverseKRec(curr, k); // head is now the tail of this group
return prev; // prev is the new head of this group
}
for (const values of [[10, 20, 30, 40, 50, 60], [10, 20, 30, 40, 50]])
console.log(toStr(reverseKRec(build(values), 3)));30 20 10 60 50 40
30 20 10 50 40Time O(n) · Space O(n / k) recursion depth
Iterative — same work, constant extra space. Remember the first node of each group: after the group is reversed it is the group's tail, and the previous group's tail must be pointed at the new head of this group.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def reverse_k_iter(head, k):
curr = head
new_head = None
prev_tail = None # tail of the previous reversed group
while curr:
group_first = curr # will become this group's tail
prev = None
count = 0
while curr and count < k: # reverse one group
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
count += 1
if new_head is None:
new_head = prev # first group's new head is the list's head
else:
prev_tail.next = prev # link previous group to this one
prev_tail = group_first
return new_head
for values in ([10, 20, 30, 40, 50, 60], [10, 20, 30, 40, 50]):
print(to_str(reverse_k_iter(build(values), 3)))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* reverseKIter(Node* head, int k) {
Node* curr = head;
Node* newHead = nullptr;
Node* prevTail = nullptr; // tail of the previous reversed group
while (curr) {
Node* groupFirst = curr; // will become this group's tail
Node* prev = nullptr;
int count = 0;
while (curr && count < k) { // reverse one group
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (!newHead) newHead = prev; // first group's new head is the list's head
else prevTail->next = prev; // link previous group to this one
prevTail = groupFirst;
}
return newHead;
}
int main() {
for (vector<int> values : {vector<int>{10, 20, 30, 40, 50, 60}, vector<int>{10, 20, 30, 40, 50}})
cout << toStr(reverseKIter(build(values), 3)) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node reverseKIter(Node head, int k) {
Node curr = head, newHead = null;
Node prevTail = null; // tail of the previous reversed group
while (curr != null) {
Node groupFirst = curr; // will become this group's tail
Node prev = null;
int count = 0;
while (curr != null && count < k) { // reverse one group
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (newHead == null) newHead = prev; // first group's new head is the list's head
else prevTail.next = prev; // link previous group to this one
prevTail = groupFirst;
}
return newHead;
}
public static void main(String[] args) {
for (int[] values : new int[][]{{10, 20, 30, 40, 50, 60}, {10, 20, 30, 40, 50}})
System.out.println(toStr(reverseKIter(build(values), 3)));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function reverseKIter(head, k) {
let curr = head, newHead = null;
let prevTail = null; // tail of the previous reversed group
while (curr) {
const groupFirst = curr; // will become this group's tail
let prev = null, count = 0;
while (curr && count < k) { // reverse one group
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (!newHead) newHead = prev; // first group's new head is the list's head
else prevTail.next = prev; // link previous group to this one
prevTail = groupFirst;
}
return newHead;
}
for (const values of [[10, 20, 30, 40, 50, 60], [10, 20, 30, 40, 50]])
console.log(toStr(reverseKIter(build(values), 3)));30 20 10 60 50 40
30 20 10 50 40Time O(n) · Space O(1)
Detect a loop — hash set of visited nodes
10 → 20 → 30 → 40 → 50
↑ │
└──────────┘ 50.next = 30 — a traversal never endsclass Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def has_loop_set(head):
seen = set()
curr = head
while curr:
if curr in seen: # visited before → we went round a loop
return True
seen.add(curr) # nodes hash by identity, not by value
curr = curr.next
return False
head = build([10, 20, 30, 40, 50])
print("10 → 20 → 30 → 40 → 50:", "Yes" if has_loop_set(head) else "No")
tail = head
while tail.next:
tail = tail.next
tail.next = head.next.next # 50 → 30 creates the loop
print("with 50 → 30:", "Yes" if has_loop_set(head) else "No")10 → 20 → 30 → 40 → 50: No
with 50 → 30: YesTime O(n) · Space O(n)
Detect a loop — Floyd's cycle detection
Initialise
slow = head,fast = head.Advance
Each step:
slow = slow.next,fast = fast.next.next. Stop with “no loop” whenfastorfast.nextisnull.Compare
If
slowis the same node asfast, there is a loop.
Why they must meet. fast enters the loop no later than slow. Suppose that when slow enters the loop, fast is k nodes ahead of it (0 ≤ k < n for a loop of length n) — equivalently, fast is n − k nodes behind slow going round the circle. Every step slow moves one and fast moves two, so the gap behind closes by exactly one node per step. After n − k steps the gap is zero: they stand on the same node. Because the gap shrinks by one (not two), fast can never jump over slow.
10 → 20 → 30 → 40 → 50 → (back to 30) loop length n = 3
step slow fast
0 10 10
1 20 30
2 30 50
3 40 40 ← meetclass Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def has_loop(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
if slow is fast: # same node (not same value) → loop
return True
return False # fast ran off the end
head = build([10, 20, 30, 40, 50])
print("10 → 20 → 30 → 40 → 50:", "Yes" if has_loop(head) else "No")
tail = head
while tail.next:
tail = tail.next
tail.next = head.next.next # 50 → 30 creates the loop
print("with 50 → 30:", "Yes" if has_loop(head) else "No")#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
bool hasLoop(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next; // one step
fast = fast->next->next; // two steps
if (slow == fast) return true; // same address → loop
}
return false; // fast ran off the end
}
int main() {
Node* head = build({10, 20, 30, 40, 50});
cout << "10 → 20 → 30 → 40 → 50: " << (hasLoop(head) ? "Yes" : "No") << "\n";
Node* tail = head;
while (tail->next) tail = tail->next;
tail->next = head->next->next; // 50 → 30 creates the loop
cout << "with 50 → 30: " << (hasLoop(head) ? "Yes" : "No") << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static boolean hasLoop(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
if (slow == fast) return true; // same reference → loop
}
return false; // fast ran off the end
}
public static void main(String[] args) {
Node head = build(new int[]{10, 20, 30, 40, 50});
System.out.println("10 → 20 → 30 → 40 → 50: " + (hasLoop(head) ? "Yes" : "No"));
Node tail = head;
while (tail.next != null) tail = tail.next;
tail.next = head.next.next; // 50 → 30 creates the loop
System.out.println("with 50 → 30: " + (hasLoop(head) ? "Yes" : "No"));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function hasLoop(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; // one step
fast = fast.next.next; // two steps
if (slow === fast) return true; // same object → loop
}
return false; // fast ran off the end
}
const head = build([10, 20, 30, 40, 50]);
console.log("10 → 20 → 30 → 40 → 50:", hasLoop(head) ? "Yes" : "No");
let tail = head;
while (tail.next) tail = tail.next;
tail.next = head.next.next; // 50 → 30 creates the loop
console.log("with 50 → 30:", hasLoop(head) ? "Yes" : "No");10 → 20 → 30 → 40 → 50: No
with 50 → 30: YesTime O(n) · Space O(1)
Detect and remove a loop
Detect
Run Floyd's algorithm. If
slowandfastnever meet, there is no loop — stop.Loop length (variation 1)
From the meeting point, walk round until you are back: the number of steps is the loop length
n.First node of the loop (variation 2)
Put
slowathead, leavefastat the meeting point. Move both one step until they are equal — that node is the loop start.Cut
From the loop start, walk until
node.nextis the loop start again; that node is the last node of the loop. Set itsnext = null.
Why moving one pointer back to the head works. Let m be the distance from head to the loop start, n the loop length, and k the distance from the loop start to the meeting point. When they meet, slow has walked m + k + x·n and fast twice that, m + k + y·n, for some lap counts x, y:
2(m + k + x·n) = m + k + y·n ⟹ m + k = (y − 2x)·n
So m + k is a multiple of the loop length. A pointer that starts at the meeting point (already k into the loop) and walks m more steps is m + k ≡ 0 (mod n) into the loop — i.e. back at the loop start. A pointer that starts at head and walks m steps is also at the loop start. Walking both at the same speed, they coincide for the first time exactly there.
10 → 15 → 5 → 20 → (back to 15) m = 1, n = 3
Floyd: slow 10,15,5,20 fast 10,5,15,20 → meet at 20 (k = 2, m + k = 3 = n ✓)
phase 2: slow = head = 10, fast = 20
one step each: slow → 15, fast → 15 → loop starts at 15
cut: from 15 walk to the node whose next is 15: that is 20 → 20.next = ∅class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def detect_and_remove(head):
slow = fast = head
while fast and fast.next: # 1. Floyd: find a meeting point
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
print("no loop")
return
length = 1 # 2. loop length: walk round once
p = fast.next
while p is not fast:
p = p.next
length += 1
print("loop length:", length)
slow = head # 3. loop start: same speed from head and meeting point
while slow is not fast:
slow = slow.next
fast = fast.next
print("loop starts at:", slow.data)
last = slow # 4. find the last node of the loop and cut
while last.next is not slow:
last = last.next
last.next = None
head = build([10, 15, 5, 20])
head.next.next.next.next = head.next # 20 → 15 creates the loop
detect_and_remove(head)
print("after removal:", to_str(head))
detect_and_remove(head) # run again: the list is clean now#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
void detectAndRemove(Node* head) {
Node* slow = head;
Node* fast = head;
bool met = false;
while (fast && fast->next) { // 1. Floyd: find a meeting point
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { met = true; break; }
}
if (!met) { cout << "no loop\n"; return; }
int length = 1; // 2. loop length: walk round once
for (Node* p = fast->next; p != fast; p = p->next) length++;
cout << "loop length: " << length << "\n";
slow = head; // 3. loop start: same speed from head and meeting point
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
cout << "loop starts at: " << slow->data << "\n";
Node* last = slow; // 4. find the last node of the loop and cut
while (last->next != slow) last = last->next;
last->next = nullptr;
}
int main() {
Node* head = build({10, 15, 5, 20});
head->next->next->next->next = head->next; // 20 → 15 creates the loop
detectAndRemove(head);
cout << "after removal: " << toStr(head) << "\n";
detectAndRemove(head); // run again: the list is clean now
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static void detectAndRemove(Node head) {
Node slow = head, fast = head;
boolean met = false;
while (fast != null && fast.next != null) { // 1. Floyd: find a meeting point
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { met = true; break; }
}
if (!met) { System.out.println("no loop"); return; }
int length = 1; // 2. loop length: walk round once
for (Node p = fast.next; p != fast; p = p.next) length++;
System.out.println("loop length: " + length);
slow = head; // 3. loop start: same speed from head and meeting point
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
System.out.println("loop starts at: " + slow.data);
Node last = slow; // 4. find the last node of the loop and cut
while (last.next != slow) last = last.next;
last.next = null;
}
public static void main(String[] args) {
Node head = build(new int[]{10, 15, 5, 20});
head.next.next.next.next = head.next; // 20 → 15 creates the loop
detectAndRemove(head);
System.out.println("after removal: " + toStr(head));
detectAndRemove(head); // run again: the list is clean now
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function detectAndRemove(head) {
let slow = head, fast = head, met = false;
while (fast && fast.next) { // 1. Floyd: find a meeting point
slow = slow.next;
fast = fast.next.next;
if (slow === fast) { met = true; break; }
}
if (!met) { console.log("no loop"); return; }
let length = 1; // 2. loop length: walk round once
for (let p = fast.next; p !== fast; p = p.next) length++;
console.log("loop length:", length);
slow = head; // 3. loop start: same speed from head and meeting point
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
console.log("loop starts at:", slow.data);
let last = slow; // 4. find the last node of the loop and cut
while (last.next !== slow) last = last.next;
last.next = null;
}
const head = build([10, 15, 5, 20]);
head.next.next.next.next = head.next; // 20 → 15 creates the loop
detectAndRemove(head);
console.log("after removal:", toStr(head));
detectAndRemove(head); // run again: the list is clean nowloop length: 3
loop starts at: 15
after removal: 10 15 5 20
no loopTime O(n) · Space O(1)
Intersection point of two linked lists
A: 5 → 8 → 7 ─┐
├─▶ 10 → 12 → 15 → ∅
B: 9 ───┘Baseline — hash set of nodes. Put every node of A in a set, then walk B and return the first node already present. O(m + n) time, O(m) space.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def intersection_set(a, b):
seen = set()
while a:
seen.add(a) # node identity, not value
a = a.next
while b:
if b in seen:
return b
b = b.next
return None
a = build([5, 8, 7, 10, 12, 15])
b = Node(9)
b.next = a.next.next.next # 9 → 10 → 12 → 15, sharing from 10
node = intersection_set(a, b)
print("intersection:", node.data if node else "none")intersection: 10Efficient — align the lengths. Both lists share their whole tail from the intersection on, so they differ only in the number of nodes before it. Count both lengths, advance the longer list's pointer by the difference, then walk both together; the first time the two pointers are the same node is the intersection (or both reach null).
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def length(head):
n = 0
while head:
n += 1
head = head.next
return n
def intersection(a, b):
la, lb = length(a), length(b)
while la > lb: # advance the longer list by the difference
a = a.next
la -= 1
while lb > la:
b = b.next
lb -= 1
while a is not b: # same distance from the end: walk together
a = a.next
b = b.next
return a # None when both ran off the end
a = build([5, 8, 7, 10, 12, 15])
b = Node(9)
b.next = a.next.next.next # 9 → 10 → 12 → 15, sharing from 10
print("A:", to_str(a))
print("B:", to_str(b))
node = intersection(a, b)
print("intersection:", node.data if node else "none")
node = intersection(a, build([1, 2]))
print("intersection with 1 → 2:", node.data if node else "none")#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
int length(Node* head) {
int n = 0;
for (Node* c = head; c; c = c->next) n++;
return n;
}
Node* intersection(Node* a, Node* b) {
int la = length(a), lb = length(b);
while (la > lb) { a = a->next; la--; } // advance the longer list by the difference
while (lb > la) { b = b->next; lb--; }
while (a != b) { // same distance from the end: walk together
a = a->next;
b = b->next;
}
return a; // nullptr when both ran off the end
}
int main() {
Node* a = build({5, 8, 7, 10, 12, 15});
Node* b = new Node(9);
b->next = a->next->next->next; // 9 → 10 → 12 → 15, sharing from 10
cout << "A: " << toStr(a) << "\n";
cout << "B: " << toStr(b) << "\n";
Node* node = intersection(a, b);
cout << "intersection: " << (node ? to_string(node->data) : "none") << "\n";
node = intersection(a, build({1, 2}));
cout << "intersection with 1 → 2: " << (node ? to_string(node->data) : "none") << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static int length(Node head) {
int n = 0;
for (Node c = head; c != null; c = c.next) n++;
return n;
}
static Node intersection(Node a, Node b) {
int la = length(a), lb = length(b);
while (la > lb) { a = a.next; la--; } // advance the longer list by the difference
while (lb > la) { b = b.next; lb--; }
while (a != b) { // same distance from the end: walk together
a = a.next;
b = b.next;
}
return a; // null when both ran off the end
}
public static void main(String[] args) {
Node a = build(new int[]{5, 8, 7, 10, 12, 15});
Node b = new Node(9);
b.next = a.next.next.next; // 9 → 10 → 12 → 15, sharing from 10
System.out.println("A: " + toStr(a));
System.out.println("B: " + toStr(b));
Node node = intersection(a, b);
System.out.println("intersection: " + (node != null ? String.valueOf(node.data) : "none"));
node = intersection(a, build(new int[]{1, 2}));
System.out.println("intersection with 1 → 2: " + (node != null ? String.valueOf(node.data) : "none"));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function length(head) {
let n = 0;
for (let c = head; c; c = c.next) n++;
return n;
}
function intersection(a, b) {
let la = length(a), lb = length(b);
while (la > lb) { a = a.next; la--; } // advance the longer list by the difference
while (lb > la) { b = b.next; lb--; }
while (a !== b) { // same distance from the end: walk together
a = a.next;
b = b.next;
}
return a; // null when both ran off the end
}
const a = build([5, 8, 7, 10, 12, 15]);
const b = new Node(9);
b.next = a.next.next.next; // 9 → 10 → 12 → 15, sharing from 10
console.log("A:", toStr(a));
console.log("B:", toStr(b));
let node = intersection(a, b);
console.log("intersection:", node ? node.data : "none");
node = intersection(a, build([1, 2]));
console.log("intersection with 1 → 2:", node ? node.data : "none");A: 5 8 7 10 12 15
B: 9 10 12 15
intersection: 10
intersection with 1 → 2: noneTime O(m + n) · Space O(1)
Segregate even and odd nodes
Naive — move odd nodes to the end. Find the last node, then traverse once more: every odd node is detached and appended after the current last node. Stop after processing the original last node, otherwise the nodes you just appended are visited again and the loop never ends.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def segregate_naive(head):
if head is None:
return None
last = head
while last.next:
last = last.next
stop = last # original last node: do not go past it
dummy = Node(0)
dummy.next = head
prev, curr = dummy, head
while True:
nxt = curr.next
if curr.data % 2 == 1: # odd: detach and append after last
prev.next = nxt
last.next = curr
curr.next = None
last = curr
else:
prev = curr
if curr is stop:
break
curr = nxt
return dummy.next
print(to_str(segregate_naive(build([17, 15, 8, 12, 5]))))
print(to_str(segregate_naive(build([1, 3, 5]))))8 12 17 15 5
1 3 5One traversal — build two sublists and join them. Keep the start and end of an even sublist and of an odd sublist. Every node is appended to the end of its own sublist as it is visited, so each sublist keeps the original relative order. At the end, link the even tail to the odd head and terminate the odd tail.
input: 17 → 15 → 8 → 12 → 5
evens: 8 → 12 even_start = 8, even_end = 12
odds: 17 → 15 → 5 odd_start = 17, odd_end = 5
join: 8 → 12 → 17 → 15 → 5 → ∅ even_end.next = odd_start, odd_end.next = ∅class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def segregate(head):
even_start = even_end = None
odd_start = odd_end = None
curr = head
while curr:
if curr.data % 2 == 0:
if even_start is None:
even_start = even_end = curr
else:
even_end.next = curr # append to the even chain
even_end = curr
else:
if odd_start is None:
odd_start = odd_end = curr
else:
odd_end.next = curr # append to the odd chain
odd_end = curr
curr = curr.next
if even_start is None or odd_start is None:
return head # all even or all odd: nothing to do
even_end.next = odd_start # join the chains
odd_end.next = None # terminate — or the list gets a cycle
return even_start
for values in ([17, 15, 8, 12, 5], [1, 3, 5], [1, 2, 4]):
print(to_str(segregate(build(values))))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* segregate(Node* head) {
Node *evenStart = nullptr, *evenEnd = nullptr;
Node *oddStart = nullptr, *oddEnd = nullptr;
for (Node* curr = head; curr; curr = curr->next) {
if (curr->data % 2 == 0) {
if (!evenStart) evenStart = evenEnd = curr;
else { evenEnd->next = curr; evenEnd = curr; } // append to the even chain
} else {
if (!oddStart) oddStart = oddEnd = curr;
else { oddEnd->next = curr; oddEnd = curr; } // append to the odd chain
}
}
if (!evenStart || !oddStart) return head; // all even or all odd: nothing to do
evenEnd->next = oddStart; // join the chains
oddEnd->next = nullptr; // terminate — or the list gets a cycle
return evenStart;
}
int main() {
for (vector<int> values : {vector<int>{17, 15, 8, 12, 5}, vector<int>{1, 3, 5}, vector<int>{1, 2, 4}})
cout << toStr(segregate(build(values))) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node segregate(Node head) {
Node evenStart = null, evenEnd = null, oddStart = null, oddEnd = null;
for (Node curr = head; curr != null; curr = curr.next) {
if (curr.data % 2 == 0) {
if (evenStart == null) evenStart = evenEnd = curr;
else { evenEnd.next = curr; evenEnd = curr; } // append to the even chain
} else {
if (oddStart == null) oddStart = oddEnd = curr;
else { oddEnd.next = curr; oddEnd = curr; } // append to the odd chain
}
}
if (evenStart == null || oddStart == null) return head; // all even or all odd
evenEnd.next = oddStart; // join the chains
oddEnd.next = null; // terminate — or the list gets a cycle
return evenStart;
}
public static void main(String[] args) {
for (int[] values : new int[][]{{17, 15, 8, 12, 5}, {1, 3, 5}, {1, 2, 4}})
System.out.println(toStr(segregate(build(values))));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function segregate(head) {
let evenStart = null, evenEnd = null, oddStart = null, oddEnd = null;
for (let curr = head; curr; curr = curr.next) {
if (curr.data % 2 === 0) {
if (!evenStart) evenStart = evenEnd = curr;
else { evenEnd.next = curr; evenEnd = curr; } // append to the even chain
} else {
if (!oddStart) oddStart = oddEnd = curr;
else { oddEnd.next = curr; oddEnd = curr; } // append to the odd chain
}
}
if (!evenStart || !oddStart) return head; // all even or all odd: nothing to do
evenEnd.next = oddStart; // join the chains
oddEnd.next = null; // terminate — or the list gets a cycle
return evenStart;
}
for (const values of [[17, 15, 8, 12, 5], [1, 3, 5], [1, 2, 4]])
console.log(toStr(segregate(build(values))));8 12 17 15 5
1 3 5
2 4 1Time O(n) · Space O(1)
Pairwise swap nodes
Swap the data. Walk two nodes at a time and exchange the values of each pair. Trivial — but it only works when swapping values is allowed and cheap. If nodes carry large payloads, or other code holds references to specific nodes (an LRU cache, an iterator), the values must stay with their nodes and the links have to be swapped instead.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def pairwise_swap_data(head):
curr = head
while curr and curr.next: # at least one node ahead
curr.data, curr.next.data = curr.next.data, curr.data
curr = curr.next.next # jump over the pair
return head
for values in ([1, 2, 3, 4], [1, 2, 3, 4, 5]):
print(to_str(pairwise_swap_data(build(values))))2 1 4 3
2 1 4 3 5Time O(n) · Space O(1)
Swap the links. For each pair a → b, make the node before the pair point at b, b point at a, and a point at whatever followed b. A dummy node in front of the head removes the special case for the first pair (whose “node before” would otherwise not exist), and the new head is simply dummy.next.
prev → a → b → rest before
a.next = b.next : prev → a ─────▶ rest
b ──▶ rest
b.next = a : b → a → rest
prev.next = b : prev → b → a → rest
prev = a : ready for the next pairclass Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def pairwise_swap(head):
dummy = Node(0) # sits before the head: no special first pair
dummy.next = head
prev = dummy
while prev.next and prev.next.next:
a = prev.next # first node of the pair
b = a.next # second node of the pair
a.next = b.next # a now points past the pair
b.next = a # b points back at a
prev.next = b # the node before the pair points at b
prev = a # a is the pair's new tail
return dummy.next
for values in ([1, 2, 3, 4], [1, 2, 3, 4, 5]):
print(to_str(pairwise_swap(build(values))))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* pairwiseSwap(Node* head) {
Node dummy(0); // sits before the head: no special first pair
dummy.next = head;
Node* prev = &dummy;
while (prev->next && prev->next->next) {
Node* a = prev->next; // first node of the pair
Node* b = a->next; // second node of the pair
a->next = b->next; // a now points past the pair
b->next = a; // b points back at a
prev->next = b; // the node before the pair points at b
prev = a; // a is the pair's new tail
}
return dummy.next;
}
int main() {
for (vector<int> values : {vector<int>{1, 2, 3, 4}, vector<int>{1, 2, 3, 4, 5}})
cout << toStr(pairwiseSwap(build(values))) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node pairwiseSwap(Node head) {
Node dummy = new Node(0); // sits before the head: no special first pair
dummy.next = head;
Node prev = dummy;
while (prev.next != null && prev.next.next != null) {
Node a = prev.next; // first node of the pair
Node b = a.next; // second node of the pair
a.next = b.next; // a now points past the pair
b.next = a; // b points back at a
prev.next = b; // the node before the pair points at b
prev = a; // a is the pair's new tail
}
return dummy.next;
}
public static void main(String[] args) {
for (int[] values : new int[][]{{1, 2, 3, 4}, {1, 2, 3, 4, 5}})
System.out.println(toStr(pairwiseSwap(build(values))));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function pairwiseSwap(head) {
const dummy = new Node(0); // sits before the head: no special first pair
dummy.next = head;
let prev = dummy;
while (prev.next && prev.next.next) {
const a = prev.next; // first node of the pair
const b = a.next; // second node of the pair
a.next = b.next; // a now points past the pair
b.next = a; // b points back at a
prev.next = b; // the node before the pair points at b
prev = a; // a is the pair's new tail
}
return dummy.next;
}
for (const values of [[1, 2, 3, 4], [1, 2, 3, 4, 5]])
console.log(toStr(pairwiseSwap(build(values))));2 1 4 3
2 1 4 3 5Time O(n) · Space O(1)
Clone a linked list with random pointers
Each node has a second pointer, random, to any node in the list (or null). A plain copy that walks next cannot set random on the copies because the target copy may not exist yet — and even when it does, you have to find it. Two solutions: a map from original to copy, or a trick that stores the mapping inside the list itself.
┌─────────────────┐
│ ┌────────┼───────┐
▼ │ │ ▼
1 ───▶ 2 ───▶ 3 ───▶ 4 next (solid)
│ ▲ │ ▲ random: 1→3, 2→1, 3→4, 4→2
└──────┼────────┘ │
└─────────────────┘Method 1 — dictionary from original to copy. Pass 1 creates a copy of every node and records copy_of[original] = copy. Pass 2 sets copy_of[node].next = copy_of[node.next] and copy_of[node].random = copy_of[node.random]; mapping null → null makes the end of the list and missing randoms fall out for free.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def pairs(head): # "data:random data:random …"
parts = []
while head:
parts.append(f"{head.data}:{head.random.data if head.random else '-'}")
head = head.next
return " ".join(parts)
def clone(head):
copy_of = {None: None} # original → copy; None maps to None
curr = head
while curr: # pass 1: create the copies
copy_of[curr] = Node(curr.data)
curr = curr.next
curr = head
while curr: # pass 2: wire next and random via the map
copy_of[curr].next = copy_of[curr.next]
copy_of[curr].random = copy_of[curr.random]
curr = curr.next
return copy_of[head]
nodes = [Node(v) for v in (1, 2, 3, 4)]
for i in range(3):
nodes[i].next = nodes[i + 1]
for i, r in enumerate((2, 0, 3, 1)): # 1→3, 2→1, 3→4, 4→2
nodes[i].random = nodes[r]
head = nodes[0]
copy = clone(head)
print("original:", pairs(head))
print("clone: ", pairs(copy))
print("after adding 100 to every original node")
for n in nodes:
n.data += 100
print("original:", pairs(head))
print("clone: ", pairs(copy)) # unchanged: it shares no node with the original#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct Node {
int data; Node* next; Node* random;
Node(int d) : data(d), next(nullptr), random(nullptr) {}
};
string pairs(Node* head) { // "data:random data:random …"
string s;
for (Node* c = head; c; c = c->next)
s += to_string(c->data) + ":" + (c->random ? to_string(c->random->data) : "-") + (c->next ? " " : "");
return s;
}
Node* clone(Node* head) {
unordered_map<Node*, Node*> copyOf; // original → copy
copyOf[nullptr] = nullptr; // nullptr maps to nullptr
for (Node* c = head; c; c = c->next) // pass 1: create the copies
copyOf[c] = new Node(c->data);
for (Node* c = head; c; c = c->next) { // pass 2: wire next and random via the map
copyOf[c]->next = copyOf[c->next];
copyOf[c]->random = copyOf[c->random];
}
return copyOf[head];
}
int main() {
vector<Node*> nodes;
for (int v : {1, 2, 3, 4}) nodes.push_back(new Node(v));
for (int i = 0; i < 3; i++) nodes[i]->next = nodes[i + 1];
int r[] = {2, 0, 3, 1}; // 1→3, 2→1, 3→4, 4→2
for (int i = 0; i < 4; i++) nodes[i]->random = nodes[r[i]];
Node* head = nodes[0];
Node* copy = clone(head);
cout << "original: " << pairs(head) << "\n";
cout << "clone: " << pairs(copy) << "\n";
cout << "after adding 100 to every original node\n";
for (Node* n : nodes) n->data += 100;
cout << "original: " << pairs(head) << "\n";
cout << "clone: " << pairs(copy) << "\n"; // unchanged: shares no node with the original
}import java.util.HashMap;
import java.util.Map;
public class Main {
static class Node {
int data; Node next, random;
Node(int d) { data = d; }
}
static String pairs(Node head) { // "data:random data:random …"
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next)
sb.append(c.data).append(':').append(c.random != null ? String.valueOf(c.random.data) : "-").append(c.next != null ? " " : "");
return sb.toString();
}
static Node clone(Node head) {
Map<Node, Node> copyOf = new HashMap<>(); // original → copy
copyOf.put(null, null); // null maps to null
for (Node c = head; c != null; c = c.next) // pass 1: create the copies
copyOf.put(c, new Node(c.data));
for (Node c = head; c != null; c = c.next) { // pass 2: wire next and random via the map
copyOf.get(c).next = copyOf.get(c.next);
copyOf.get(c).random = copyOf.get(c.random);
}
return copyOf.get(head);
}
public static void main(String[] args) {
Node[] nodes = new Node[4];
for (int i = 0; i < 4; i++) nodes[i] = new Node(i + 1);
for (int i = 0; i < 3; i++) nodes[i].next = nodes[i + 1];
int[] r = {2, 0, 3, 1}; // 1→3, 2→1, 3→4, 4→2
for (int i = 0; i < 4; i++) nodes[i].random = nodes[r[i]];
Node head = nodes[0];
Node copy = clone(head);
System.out.println("original: " + pairs(head));
System.out.println("clone: " + pairs(copy));
System.out.println("after adding 100 to every original node");
for (Node n : nodes) n.data += 100;
System.out.println("original: " + pairs(head));
System.out.println("clone: " + pairs(copy)); // unchanged: shares no node with the original
}
}class Node {
constructor(data) { this.data = data; this.next = null; this.random = null; }
}
function pairs(head) { // "data:random data:random …"
const parts = [];
for (let c = head; c; c = c.next) parts.push(`${c.data}:${c.random ? c.random.data : "-"}`);
return parts.join(" ");
}
function clone(head) {
const copyOf = new Map([[null, null]]); // original → copy; null maps to null
for (let c = head; c; c = c.next) // pass 1: create the copies
copyOf.set(c, new Node(c.data));
for (let c = head; c; c = c.next) { // pass 2: wire next and random via the map
copyOf.get(c).next = copyOf.get(c.next);
copyOf.get(c).random = copyOf.get(c.random);
}
return copyOf.get(head);
}
const nodes = [1, 2, 3, 4].map(v => new Node(v));
for (let i = 0; i < 3; i++) nodes[i].next = nodes[i + 1];
[2, 0, 3, 1].forEach((r, i) => { nodes[i].random = nodes[r]; }); // 1→3, 2→1, 3→4, 4→2
const head = nodes[0];
const copy = clone(head);
console.log("original:", pairs(head));
console.log("clone: ", pairs(copy));
console.log("after adding 100 to every original node");
for (const n of nodes) n.data += 100;
console.log("original:", pairs(head));
console.log("clone: ", pairs(copy)); // unchanged: shares no node with the originaloriginal: 1:3 2:1 3:4 4:2
clone: 1:3 2:1 3:4 4:2
after adding 100 to every original node
original: 101:103 102:101 103:104 104:102
clone: 1:3 2:1 3:4 4:2Time O(n) · Space O(n) for the map
Method 2 — interleave the copies, O(1) extra space. Store the mapping in the list: insert each copy right after its original, so original.next is always its copy. Then copy.random = original.random.next finds the right copy in O(1) without a map. Finally unweave the two lists.
Interleave
For every original node
o, createo'and insert it aftero:1 → 1' → 2 → 2' → 3 → 3' → 4 → 4'.Set randoms
For every original
o(step two at a time):o.next.random = o.random.next— the copy ofo.randomis the node right after it. Skip wheno.randomisnull.Unweave
Restore
o.next = o.next.nextand seto'.next = o'.next.next, splitting the chain back into the original list and the clone.
after step 1: 1 → 1' → 2 → 2' → 3 → 3' → 4 → 4'
step 2 for node 2 (random → 1): 2.next.random = 2.random.next
2'.random = 1.next = 1' ✓
after step 3: 1 → 2 → 3 → 4 original restored
1' → 2' → 3' → 4' clone, with randoms among the primed nodesclass Node:
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def pairs(head): # "data:random data:random …"
parts = []
while head:
parts.append(f"{head.data}:{head.random.data if head.random else '-'}")
head = head.next
return " ".join(parts)
def clone(head):
if head is None:
return None
curr = head
while curr: # 1. insert a copy after every original
copy = Node(curr.data)
copy.next = curr.next
curr.next = copy
curr = copy.next
curr = head
while curr: # 2. copy.random = the copy of original.random
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
clone_head = head.next
curr = head
while curr: # 3. unweave originals and copies
copy = curr.next
curr.next = copy.next
copy.next = copy.next.next if copy.next else None
curr = curr.next
return clone_head
nodes = [Node(v) for v in (1, 2, 3, 4)]
for i in range(3):
nodes[i].next = nodes[i + 1]
for i, r in enumerate((2, 0, 3, 1)): # 1→3, 2→1, 3→4, 4→2
nodes[i].random = nodes[r]
head = nodes[0]
copy = clone(head)
print("original:", pairs(head))
print("clone: ", pairs(copy))
print("after adding 100 to every original node")
for n in nodes:
n.data += 100
print("original:", pairs(head))
print("clone: ", pairs(copy))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next; Node* random;
Node(int d) : data(d), next(nullptr), random(nullptr) {}
};
string pairs(Node* head) { // "data:random data:random …"
string s;
for (Node* c = head; c; c = c->next)
s += to_string(c->data) + ":" + (c->random ? to_string(c->random->data) : "-") + (c->next ? " " : "");
return s;
}
Node* clone(Node* head) {
if (!head) return nullptr;
for (Node* curr = head; curr; curr = curr->next->next) { // 1. insert a copy after every original
Node* copy = new Node(curr->data);
copy->next = curr->next;
curr->next = copy;
}
for (Node* curr = head; curr; curr = curr->next->next) // 2. copy->random = copy of original->random
if (curr->random) curr->next->random = curr->random->next;
Node* cloneHead = head->next;
for (Node* curr = head; curr; curr = curr->next) { // 3. unweave originals and copies
Node* copy = curr->next;
curr->next = copy->next;
copy->next = copy->next ? copy->next->next : nullptr;
}
return cloneHead;
}
int main() {
vector<Node*> nodes;
for (int v : {1, 2, 3, 4}) nodes.push_back(new Node(v));
for (int i = 0; i < 3; i++) nodes[i]->next = nodes[i + 1];
int r[] = {2, 0, 3, 1}; // 1→3, 2→1, 3→4, 4→2
for (int i = 0; i < 4; i++) nodes[i]->random = nodes[r[i]];
Node* head = nodes[0];
Node* copy = clone(head);
cout << "original: " << pairs(head) << "\n";
cout << "clone: " << pairs(copy) << "\n";
cout << "after adding 100 to every original node\n";
for (Node* n : nodes) n->data += 100;
cout << "original: " << pairs(head) << "\n";
cout << "clone: " << pairs(copy) << "\n";
}public class Main {
static class Node {
int data; Node next, random;
Node(int d) { data = d; }
}
static String pairs(Node head) { // "data:random data:random …"
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next)
sb.append(c.data).append(':').append(c.random != null ? String.valueOf(c.random.data) : "-").append(c.next != null ? " " : "");
return sb.toString();
}
static Node clone(Node head) {
if (head == null) return null;
for (Node curr = head; curr != null; curr = curr.next.next) { // 1. insert a copy after every original
Node copy = new Node(curr.data);
copy.next = curr.next;
curr.next = copy;
}
for (Node curr = head; curr != null; curr = curr.next.next) // 2. copy.random = copy of original.random
if (curr.random != null) curr.next.random = curr.random.next;
Node cloneHead = head.next;
for (Node curr = head; curr != null; curr = curr.next) { // 3. unweave originals and copies
Node copy = curr.next;
curr.next = copy.next;
copy.next = copy.next != null ? copy.next.next : null;
}
return cloneHead;
}
public static void main(String[] args) {
Node[] nodes = new Node[4];
for (int i = 0; i < 4; i++) nodes[i] = new Node(i + 1);
for (int i = 0; i < 3; i++) nodes[i].next = nodes[i + 1];
int[] r = {2, 0, 3, 1}; // 1→3, 2→1, 3→4, 4→2
for (int i = 0; i < 4; i++) nodes[i].random = nodes[r[i]];
Node head = nodes[0];
Node copy = clone(head);
System.out.println("original: " + pairs(head));
System.out.println("clone: " + pairs(copy));
System.out.println("after adding 100 to every original node");
for (Node n : nodes) n.data += 100;
System.out.println("original: " + pairs(head));
System.out.println("clone: " + pairs(copy));
}
}class Node {
constructor(data) { this.data = data; this.next = null; this.random = null; }
}
function pairs(head) { // "data:random data:random …"
const parts = [];
for (let c = head; c; c = c.next) parts.push(`${c.data}:${c.random ? c.random.data : "-"}`);
return parts.join(" ");
}
function clone(head) {
if (!head) return null;
for (let curr = head; curr; curr = curr.next.next) { // 1. insert a copy after every original
const copy = new Node(curr.data);
copy.next = curr.next;
curr.next = copy;
}
for (let curr = head; curr; curr = curr.next.next) // 2. copy.random = copy of original.random
if (curr.random) curr.next.random = curr.random.next;
const cloneHead = head.next;
for (let curr = head; curr; curr = curr.next) { // 3. unweave originals and copies
const copy = curr.next;
curr.next = copy.next;
copy.next = copy.next ? copy.next.next : null;
}
return cloneHead;
}
const nodes = [1, 2, 3, 4].map(v => new Node(v));
for (let i = 0; i < 3; i++) nodes[i].next = nodes[i + 1];
[2, 0, 3, 1].forEach((r, i) => { nodes[i].random = nodes[r]; }); // 1→3, 2→1, 3→4, 4→2
const head = nodes[0];
const copy = clone(head);
console.log("original:", pairs(head));
console.log("clone: ", pairs(copy));
console.log("after adding 100 to every original node");
for (const n of nodes) n.data += 100;
console.log("original:", pairs(head));
console.log("clone: ", pairs(copy));original: 1:3 2:1 3:4 4:2
clone: 1:3 2:1 3:4 4:2
after adding 100 to every original node
original: 101:103 102:101 103:104 104:102
clone: 1:3 2:1 3:4 4:2Time O(n) · Space O(1) extra (the clone itself is O(n))
Merge two sorted linked lists
a: 10 → 20 → 30 b: 5 → 25
dummy → 5 take b (5 ≤ 10)
dummy → 5 → 10 take a
dummy → 5 → 10 → 20 take a
dummy → 5 → 10 → 20 → 25 take b
dummy → 5 → 10 → 20 → 25 → 30 a has 30 left: link the restclass Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def merge(a, b):
dummy = Node(0) # result tail always exists
tail = dummy
while a and b:
if a.data <= b.data: # take the smaller head (<= keeps it stable)
tail.next = a
a = a.next
else:
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a else b # the rest of the other list is already sorted
return dummy.next
print(to_str(merge(build([10, 20, 30]), build([5, 25]))))
print(to_str(merge(build([1, 3, 5]), build([2, 4, 6]))))
print(to_str(merge(build([1, 2, 3]), None)))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* merge(Node* a, Node* b) {
Node dummy(0); // result tail always exists
Node* tail = &dummy;
while (a && b) {
if (a->data <= b->data) { // take the smaller head (<= keeps it stable)
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? a : b; // the rest of the other list is already sorted
return dummy.next;
}
int main() {
cout << toStr(merge(build({10, 20, 30}), build({5, 25}))) << "\n";
cout << toStr(merge(build({1, 3, 5}), build({2, 4, 6}))) << "\n";
cout << toStr(merge(build({1, 2, 3}), nullptr)) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node merge(Node a, Node b) {
Node dummy = new Node(0); // result tail always exists
Node tail = dummy;
while (a != null && b != null) {
if (a.data <= b.data) { // take the smaller head (<= keeps it stable)
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a != null ? a : b; // the rest of the other list is already sorted
return dummy.next;
}
public static void main(String[] args) {
System.out.println(toStr(merge(build(new int[]{10, 20, 30}), build(new int[]{5, 25}))));
System.out.println(toStr(merge(build(new int[]{1, 3, 5}), build(new int[]{2, 4, 6}))));
System.out.println(toStr(merge(build(new int[]{1, 2, 3}), null)));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function merge(a, b) {
const dummy = new Node(0); // result tail always exists
let tail = dummy;
while (a && b) {
if (a.data <= b.data) { // take the smaller head (<= keeps it stable)
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a ? a : b; // the rest of the other list is already sorted
return dummy.next;
}
console.log(toStr(merge(build([10, 20, 30]), build([5, 25]))));
console.log(toStr(merge(build([1, 3, 5]), build([2, 4, 6]))));
console.log(toStr(merge(build([1, 2, 3]), null)));5 10 20 25 30
1 2 3 4 5 6
1 2 3Time O(m + n) · Space O(1)
The same idea reads naturally as recursion — the head of the merged list is the smaller head, and its next is the merge of what remains. Elegant, but it uses one stack frame per node, so keep it for short lists:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def merge_rec(a, b):
if a is None:
return b
if b is None:
return a
if a.data <= b.data:
a.next = merge_rec(a.next, b) # a is the head, merge the rest behind it
return a
b.next = merge_rec(a, b.next)
return b
print(to_str(merge_rec(build([10, 20, 30]), build([5, 25]))))5 10 20 25 30Palindrome linked list
Naive — copy the values onto a stack. Push every value, then walk the list again popping: pops come out in reverse order, so each pop must equal the current node. O(n) time but O(n) extra space.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def is_palindrome_stack(head):
stack = []
curr = head
while curr:
stack.append(curr.data)
curr = curr.next
curr = head
while curr:
if stack.pop() != curr.data: # pops come out reversed
return False
curr = curr.next
return True
for values in ([1, 2, 3, 2, 1], [1, 2, 3, 4]):
print("Yes" if is_palindrome_stack(build(values)) else "No")Yes
NoEfficient — reverse the second half in place. Find the end of the first half with slow/fast, reverse the second half, and walk the two halves together comparing values. Then reverse the second half again to restore the list — callers do not expect a read-only query to scramble their data.
1 → 2 → 3 → 2 → 1 slow stops at 3 (end of first half); second half = 2 → 1
reverse second half: 1 → 2 → 3 → 1 → 2
↑ ↑
a b compare a, b while b exists: 1=1, 2=2 → Yes
restore: 1 → 2 → 3 → 2 → 1class Node:
def __init__(self, data):
self.data = data
self.next = None
def build(values):
head = None
for v in reversed(values):
node = Node(v)
node.next = head
head = node
return head
def to_str(head):
parts = []
while head:
parts.append(str(head.data))
head = head.next
return " ".join(parts)
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prev
def is_palindrome(head):
if head is None or head.next is None:
return True
slow = fast = head
while fast.next and fast.next.next: # slow stops at the end of the first half
slow = slow.next
fast = fast.next.next
second = reverse(slow.next) # reverse the second half
a, b = head, second
same = True
while b: # second half is never longer than the first
if a.data != b.data:
same = False
break
a = a.next
b = b.next
slow.next = reverse(second) # restore the list
return same
for values in ([1, 2, 3, 2, 1], [1, 2, 3, 4], [1, 2, 2, 1]):
head = build(values)
print(to_str(head), "→", "Yes" if is_palindrome(head) else "No")
head = build([1, 2, 3, 2, 1])
is_palindrome(head)
print("list after the check:", to_str(head))#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Node {
int data; Node* next;
Node(int d) : data(d), next(nullptr) {}
};
Node* build(const vector<int>& v) {
Node* head = nullptr;
for (int i = (int)v.size() - 1; i >= 0; i--) {
Node* node = new Node(v[i]);
node->next = head;
head = node;
}
return head;
}
string toStr(Node* head) {
string s;
for (Node* c = head; c; c = c->next) s += to_string(c->data) + (c->next ? " " : "");
return s;
}
Node* reverse(Node* head) {
Node* prev = nullptr;
while (head) {
Node* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
bool isPalindrome(Node* head) {
if (!head || !head->next) return true;
Node* slow = head;
Node* fast = head;
while (fast->next && fast->next->next) { // slow stops at the end of the first half
slow = slow->next;
fast = fast->next->next;
}
Node* second = reverse(slow->next); // reverse the second half
bool same = true;
for (Node *a = head, *b = second; b; a = a->next, b = b->next) // second half is never longer
if (a->data != b->data) { same = false; break; }
slow->next = reverse(second); // restore the list
return same;
}
int main() {
for (vector<int> values : {vector<int>{1, 2, 3, 2, 1}, vector<int>{1, 2, 3, 4}, vector<int>{1, 2, 2, 1}}) {
Node* head = build(values);
cout << toStr(head) << " → " << (isPalindrome(head) ? "Yes" : "No") << "\n";
}
Node* head = build({1, 2, 3, 2, 1});
isPalindrome(head);
cout << "list after the check: " << toStr(head) << "\n";
}public class Main {
static class Node {
int data; Node next;
Node(int d) { data = d; }
}
static Node build(int[] v) {
Node head = null;
for (int i = v.length - 1; i >= 0; i--) {
Node node = new Node(v[i]);
node.next = head;
head = node;
}
return head;
}
static String toStr(Node head) {
StringBuilder sb = new StringBuilder();
for (Node c = head; c != null; c = c.next) sb.append(c.data).append(c.next != null ? " " : "");
return sb.toString();
}
static Node reverse(Node head) {
Node prev = null;
while (head != null) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
static boolean isPalindrome(Node head) {
if (head == null || head.next == null) return true;
Node slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { // slow stops at the end of the first half
slow = slow.next;
fast = fast.next.next;
}
Node second = reverse(slow.next); // reverse the second half
boolean same = true;
for (Node a = head, b = second; b != null; a = a.next, b = b.next) // second half is never longer
if (a.data != b.data) { same = false; break; }
slow.next = reverse(second); // restore the list
return same;
}
public static void main(String[] args) {
for (int[] values : new int[][]{{1, 2, 3, 2, 1}, {1, 2, 3, 4}, {1, 2, 2, 1}}) {
Node head = build(values);
System.out.println(toStr(head) + " → " + (isPalindrome(head) ? "Yes" : "No"));
}
Node head = build(new int[]{1, 2, 3, 2, 1});
isPalindrome(head);
System.out.println("list after the check: " + toStr(head));
}
}class Node {
constructor(data) { this.data = data; this.next = null; }
}
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new Node(values[i]);
node.next = head;
head = node;
}
return head;
}
function toStr(head) {
const parts = [];
for (let c = head; c; c = c.next) parts.push(c.data);
return parts.join(" ");
}
function reverse(head) {
let prev = null;
while (head) {
const next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
function isPalindrome(head) {
if (!head || !head.next) return true;
let slow = head, fast = head;
while (fast.next && fast.next.next) { // slow stops at the end of the first half
slow = slow.next;
fast = fast.next.next;
}
const second = reverse(slow.next); // reverse the second half
let same = true;
for (let a = head, b = second; b; a = a.next, b = b.next) // second half is never longer
if (a.data !== b.data) { same = false; break; }
slow.next = reverse(second); // restore the list
return same;
}
for (const values of [[1, 2, 3, 2, 1], [1, 2, 3, 4], [1, 2, 2, 1]]) {
const head = build(values);
console.log(toStr(head), "→", isPalindrome(head) ? "Yes" : "No");
}
const head = build([1, 2, 3, 2, 1]);
isPalindrome(head);
console.log("list after the check:", toStr(head));1 2 3 2 1 → Yes
1 2 3 4 → No
1 2 2 1 → Yes
list after the check: 1 2 3 2 1Time O(n) · Space O(1)
Interview Q&A
Why does Floyd's algorithm use speeds 1 and 2 — would 1 and 3 work?
How do you find the start of the loop after detecting it, and why does it work?
How would you detect a loop or find an intersection without Floyd's algorithm?
Reverse a linked list in O(1) space — iterative or recursive?
What is the dummy-head trick and when do you use it?
Clone a list with random pointers in O(1) extra space — how?
Which sorting algorithm fits a linked list best, and why not quicksort?