Microsoft Interview Question
Software DevelopersTeam: Bing
Interview Type: Written Test
find new list's end (k -1) and rearrange elements to list's head
template<typename T>
struct Node
{
T value;
Node *next;
Node(const T &val)
: value(val)
, next(nullptr)
{}
};
template<typename T>
class List
{
public:
List()
: m_head(nullptr)
, m_len(0)
{}
~List()
{
Node<T> *iter = m_head;
while (iter)
{
Node<T> *next = iter->next;
delete iter;
iter = next;
}
}
void Insert(const T value)
{
if (!m_head)
{
m_head = new Node<T>(value);
m_len++;
}
else
{
Node<T> *iter = m_head->next;
Node<T> *prev = m_head;
while (iter)
{
prev = iter;
iter = iter->next;
}
prev->next = new Node<T>(value);
m_len++;
}
}
void RotateOn(size_t k)
{
size_t mod_k = k % m_len;
if (m_head && mod_k > 0)
{
// localize new end of a list
Node<T> *iter_kth = m_head;
for (size_t i = 0; i < mod_k - 1; i++){
iter_kth = iter_kth->next;
}
// get current end-node
Node<T> *iter = iter_kth->next;
Node<T> *end = iter_kth;
while (iter)
{
end = iter;
iter = iter->next;
}
// rearrange list nodes
Node<T> *new_head = iter_kth->next;
iter_kth->next = nullptr;
end->next = m_head;
m_head = new_head;
}
}
private:
Node<T> *m_head;
size_t m_len;
};
// assuming LinkedList has a head Node member
void LinkedList::rotate(int k) {
Node* cur = head; Node* prev = null;
for (int i = 1; i < k && cur->next; ++i) {
prev = cur;
cur = cur->next;
}
if (prev && i == k) {
prev->next = 0;
Node* oldHead = head;
head = cur;
while (cur->next)
cur = cur->next;
cur-next = oldHead;
}
}
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = Node(None)
def InsertNode(self,data):
newnode = Node(data)
if self.head.next == None:
self.head.next = newnode
else:
currnode = self.head.next
while currnode.next:
currnode = currnode.next
currnode.next = newnode
def Print(self):
if self.head.next == None:
print "No Data available"
return
currnode = self.head.next
while (currnode):
print currnode.data
currnode = currnode.next
def RotateonKthElement(self,k):
if k ==1 :
print "First element can not be rotated"
return
if self.head.next == None:
print "No Data available"
return
currnode = self.head.next
i=1
while currnode.next:
if i+1 == k:
nextnode = currnode.next
currnode.next = None
currnode = nextnode
rotatenode = currnode
if currnode.next:
currnode =currnode.next
i += 1
lastnode = currnode
nexttoheadnode = self.head.next
self.head.next = rotatenode
lastnode.next = nexttoheadnode
ll = LinkedList()
ll.InsertNode(1)
ll.InsertNode(2)
ll.InsertNode(3)
ll.InsertNode(4)
ll.InsertNode(5)
ll.RotateonKthElement(4)
ll.Print() #prints 4 5 1 2 3
Go to the k-1th element,save the next as head.
Point the next of k-th element to null.
Take the last k elements of the list and point the end of it to the original head
In Scala you can do it by drop and take
def rotateList(list : List[Int], k : Int) : List[Int] = list.drop(k)++list.take(k)
RotateLinkedList.cpp
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};
void printlist(struct node* head)
{
while(head!=NULL)
{
cout<<head->data;
head=head->next;
}
}
void rotateList(struct node* head, int k)
{
int count=0;
struct node* temp=head;
struct node* current=temp;
struct node* prev=NULL;
while(count!=k)
{
prev=temp;
temp=temp->next;
current=temp;
count++;
}
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
prev->next=NULL;
cout<<"======================"<<endl;
printlist(current);
}
int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;
n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<"======================"<<endl;
rotateList(n,3);
cout<<"======================"<<endl;
return 0;
}
RotateLinkedList.cpp
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};
void printlist(struct node* head)
{
while(head!=NULL)
{
cout<<head->data;
head=head->next;
}
}
void rotateList(struct node* head, int k)
{
int count=0;
struct node* temp=head;
struct node* current=temp;
struct node* prev=NULL;
while(count!=k)
{
prev=temp;
temp=temp->next;
current=temp;
count++;
}
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
prev->next=NULL;
cout<<"======================"<<endl;
printlist(current);
}
int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;
n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<endl;
rotateList(n,3);
cout<<endl;
return 0;
}
RotateLinkedList.cpp
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node{
int data;
struct node *next;
};
void printlist(struct node* head)
{
while(head!=NULL)
{
cout<<head->data;
head=head->next;
}
}
void rotateList(struct node* head, int k)
{
int count=0;
struct node* temp=head;
struct node* current=temp;
struct node* prev=NULL;
while(count!=k)
{
prev=temp;
temp=temp->next;
current=temp;
count++;
}
while(temp->next!=NULL)
temp=temp->next;
temp->next=head;
prev->next=NULL;
cout<<"======================"<<endl;
printlist(current);
}
int main()
{
struct node* head=NULL;
struct node* n= (struct node*)malloc(sizeof(struct node));
struct node* n2=(struct node*)malloc(sizeof(struct node));
struct node* n1= (struct node*)malloc(sizeof(struct node));
struct node* n3= (struct node*)malloc(sizeof(struct node));
struct node* n4=(struct node*)malloc(sizeof(struct node));
struct node* n5=(struct node*)malloc(sizeof(struct node));
n->data=1;
n->next=n1;
n1->data=2;
n1->next=n2;
n2->data=3;
n2->next=n3;
n3->data=4;
n3->next=n4;
n4->data=5;
n4->next=n5;
n5->data=6;
n5->next=NULL;
printlist(n);
cout<<"======================"<<endl;
rotateList(n,3);
cout<<"======================"<<endl;
return 0;
}
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode * reverseK(ListNode * cur)
{
ListNode * prev=0;
ListNode * next=0;
while ( cur )
{
next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
ListNode * rotateK(ListNode * head, int k)
{
ListNode * l1 = head;
ListNode * prev = 0;
while(k--)
{
prev=head;
head=head->next;
}
if ( head == 0 )
return l1;
if (prev) prev->next=0;
ListNode* l2=head;
l2=reverseK(l2);
if ( k ) head->next=l1;
return l2;
}
public ListNode rotateRight(ListNode head, int k) {
if(head==null||head.next==null)
return head;
ListNode tempNode = new ListNode(0);
tempNode.next = head;
ListNode fastPtr = tempNode;
ListNode slowPtr = tempNode;
int len = 0;
for(;fastPtr.next!=null;len++)
fastPtr = fastPtr.next;
for(int i = len - k % len; i>0;i--)
slowPtr = slowPtr.next;
fastPtr.next = tempNode.next;
tempNode.next = slowPtr.next;
slowPtr.next = null;
return tempNode.next;
}
#include <stdio.h>
#include <stdlib.h>
struct list;
typedef struct list {
int val;
struct list *next;
} list_t;
list_t * rotate_list (list_t *head, int k)
{
int i = 1;
list_t *cur;
list_t *new_head;
if (!head)
return NULL;
if (k == 0)
return NULL;
if (k == 1)
return head;
cur = new_head = head;
while (cur) {
if (i == (k -1)) {
/* save the new head of the list */
new_head = cur->next;
/*
* Check for error condition : there are less elements in the list
* than k
*/
if (!cur->next)
return NULL;
else {
/* k -1 node is now the last one in the list */
cur->next = NULL;
cur = new_head;
}
}
if (cur->next == NULL) {
/*
* check for the case where there is only one element in the list
* Do not create a circular list in that case
*/
if (cur != head) {
cur->next = head;
cur = NULL;
}
} else {
i++;
cur = cur->next;
}
}
return new_head;
}
find kth - 1 element make it point to null, last element in linked List point to head. update head to be kth elememt
- Gear March 05, 2017