Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Keep two chains: one through the odd-position nodes, one through the even-position nodes.
  2. 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);
    }
}

Solve Odd Even Linked List online · All practice problems