Getting everything ready for you…

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

0s

Practice › Linked List

Rotate List

Medium · Linked List · Asked at Amazon, Microsoft, LinkedIn

Rotate the list to the right by k places (the last k nodes move to the front).

Input

First line: n. Second line: n values. Third line: k.

Output

The rotated list, space-separated.

Constraints

Find the length, make it circular, and break it at the right place. Remember k % n.

Example 1

Input

5
1 2 3 4 5
2

Output

4 5 1 2 3

Example 2

Input

3
0 1 2
4

Output

2 0 1

Hints

  1. Rotating by n gives back the same list, so use k % n.
  2. Connect the tail to the head to make a ring, then cut it after the (n − k)-th node — the next node is the new head.

Approach

Walk the list once to find its length n and its tail. Set k %= n; if k is 0, nothing changes. Otherwise link tail.next = head to make a ring, step n − k nodes from the old tail to reach the new tail, then make newHead = newTail.next and set newTail.next = null. k can be 2·10^9, so the modulo is required, not just an optimisation.

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;
    Node(long long v) : val(v), next(nullptr) {}
};

int main() {
    int n;
    cin >> n;
    Node dummy(0), *tail = &dummy;
    for (int i = 0; i < n; i++) {
        long long v;
        cin >> v;
        tail = tail->next = new Node(v);
    }
    long long k;
    cin >> k;
    Node *head = dummy.next;
    k %= n;
    if (k > 0) {
        tail->next = head;  // make it a ring
        Node *newTail = tail;
        for (int i = 0; i < n - k; i++) newTail = newTail->next;
        head = newTail->next;
        newTail->next = nullptr;
    }
    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, nxt=None):
        self.val, self.next = val, nxt


data = sys.stdin.read().split()
n = int(data[0])
k = int(data[n + 1]) % n
head = tail = Node(data[1])
for v in data[2 : n + 1]:
    tail.next = Node(v)
    tail = tail.next

if k:
    tail.next = head  # make it a ring
    new_tail = tail
    for _ in range(n - k):
        new_tail = new_tail.next
    head = new_tail.next
    new_tail.next = None

out = []
while head:
    out.append(head.val)
    head = head.next
print(" ".join(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), tail = dummy;
        for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
        long k = sc.nextLong() % n;
        Node head = dummy.next;
        if (k > 0) {
            tail.next = head;  // make it a ring
            Node newTail = tail;
            for (long i = 0; i < n - k; i++) newTail = newTail.next;
            head = newTail.next;
            newTail.next = null;
        }
        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 Rotate List online · All practice problems