Coderust: Hacking the Coding Interview/

...

/

Rotate a Linked List

Rotate a Linked List

Given the head of a singly linked list and an integer 'n' rotate the linked list by 'n'.

We'll cover the following...

Statement

Given the head of a singly linked list and an integer n, rotate the linked list by n and return the rotated linked list.

Example

Below is an example of sample input and expected output linked list after rotating by 22.

Note: The value of n can be larger than the length of the linked list.

Sample input

[1, 2, 3, 4, 5]
2

Expected output

[4, 5, 1, 2 ,3]

Note: For positive integers, we’ll do a positive rotation and for negative integers, we’ll do a left rotation.

g head2 result a2 4 head2->a2 b2 5 a2->b2 c2 1 b2->c2 d2 2 c2->d2 e2 3 d2->e2 head1 head a1 1 head1->a1 num1 n=2 b1 2 a1->b1 c1 3 b1->c1 d1 4 c1->d1 e1 5 d1->e1

Below is an input linked list and output after rotating by −2-2:

g head2 result a2 3 head2->a2 b2 4 a2->b2 c2 5 b2->c2 d2 1 c2->d2 e2 2 d2->e2 head1 head a1 1 head1->a1 num1 n=-2 b1 2 a1->b1 c1 3 b1->c1 d1 4 c1->d1 e1 5 d1->e1

Try it yourself

main.cpp
LinkedList.cpp
LinkedListNode.cpp
#include <vector>
#include "LinkedList.cpp"
using namespace std;
typedef LinkedListNode* NodePtr;
NodePtr RotateList(NodePtr head, int n) {
	//TODO: Write - Your - Code
	return head;
}

Solution

Naive solution

To rotate by one node, we find the last node of the linked list and make it the head of the linked list. One way of solving our original problem is to rotate by one node the last node of a linked list, nn ...