Rotate a linked list
This problem was asked by Airbnb.
Given a linked list and a positive integer k, rotate the list to the right by k places.
For example, given the linked list 7 -> 7 -> 3 -> 5
and k = 2, it should become 3 -> 5 -> 7 -> 7
.
Given the linked list 1 -> 2 -> 3 -> 4 -> 5
and k = 3, it should become 3 -> 4 -> 5 -> 1 -> 2
.
My Solution(C++):
#include <iostream>
struct node{
int data;
node *next;
// node(int a){
// data = a;
// next = nullptr;
// }
};
node *createNode(int a){
node *temp = new node;
temp->data = a;
temp->next = nullptr;
return temp;
}
class LinkedList{
private:
node *head, *tail;
int length;
public:
LinkedList();
void addNode(int);
void printLinkedList();
void rotate(int);
};
LinkedList::LinkedList(){
length = 0;
}
void LinkedList::addNode(int a){
if (length==0){
// node A = node(a);
// head = tail = &A;
head = tail = createNode(a);
} else {
// node A = node(a);
// tail->next = &A;
tail->next = createNode(a);
tail = tail->next;
}
length++;
}
void LinkedList::printLinkedList(){
node *curr = head;
while (curr->next!=nullptr){
std::cout<<curr->data<<"=>";
curr = curr->next;
}
std::cout<<curr->data<<'\n';
}
void LinkedList::rotate(int k){
node *curr = head;
for (int i=0; i<k-1; i++){
curr = curr->next;
}
tail->next = head;
head = curr->next;
curr->next = nullptr;
}
void test(){
LinkedList l1 = LinkedList();
l1.addNode(7);
l1.addNode(7);
l1.addNode(3);
l1.addNode(5);
l1.printLinkedList();
l1.rotate(2);
l1.printLinkedList();
LinkedList l2 = LinkedList();
l2.addNode(1);
l2.addNode(2);
l2.addNode(3);
l2.addNode(4);
l2.addNode(5);
l2.printLinkedList();
l2.rotate(3);
l2.printLinkedList();
}
int main(){
test();
return 0;
}