Practice › Linked List
Odd Even Linked List
Medium · Linked List · Asked at Amazon, Microsoft, Adobe
Reorder the list so that all nodes at odd positions (1st, 3rd, 5th, …) come first, followed by all nodes at even positions, keeping the relative order inside each group. Print the result.
Input
First line: n. Second line: the n node values from head to tail.
Output
The reordered list.
Constraints
- 1 ≤ n ≤ 10^5
Keep two chains (odd and even) while walking the list once, then attach the even chain after the odd one.
Example 1
Input
5 1 2 3 4 5
Output
1 3 5 2 4
Example 2
Input
7 2 1 3 5 6 4 7
Output
2 3 6 7 1 5 4
Hints
- Keep two chains: one through the odd-position nodes, one through the even-position nodes.
- Advance both by relinking odd.next = even.next and even.next = odd.next; finally attach the even chain after the last odd node.
Approach
odd = head, even = head.next, and remember evenHead. While even and even.next exist: odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next. This splits the list into two chains in place without changing relative order. Then odd.next = evenHead.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
Node(long long v) : val(v) {}
};
int main() {
int n;
cin >> n;
Node dummy(0), *t = &dummy;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
t = t->next = new Node(x);
}
Node *head = dummy.next;
if (head->next) {
Node *odd = head, *even = head->next, *evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
}
for (Node *p = head; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.next = val, None
data = list(map(int, sys.stdin.read().split()))
dummy = tail = Node(0)
for v in data[1 : 1 + data[0]]:
tail.next = Node(v)
tail = tail.next
head = dummy.next
if head.next:
odd, even = head, head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
out, p = [], head
while p:
out.append(p.val)
p = p.next
print(*out)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), t = dummy;
for (int i = 0; i < n; i++) t = t.next = new Node(sc.nextLong());
Node head = dummy.next;
if (head.next != null) {
Node odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
}
StringBuilder sb = new StringBuilder();
for (Node p = head; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}