Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
I don't agree with that, Copy my code, and run it with your input...i am getting the desired result.
@Shashi in the Q u have mentioned "Reverse the linked-list till k elements and then traverse till m elements and repeat."
can you explain what u mean by "repeat" are we supposed to alternatively reverse k elements after every m elements?
If I am understanding it right it should be
I/P 1->2->3->4->5->6->7->8->9 k=2 m=3;
O/P 2->1->3->4->5->7->6->8->9 ????
@Anonymous ...Shashi's code will work fine in your case
@shashi ...However there is a basic flaw for which i didnt had to run the code.. which is the head of linked list is not being updated and hence
I/P 1->2->3->4->5->6->7->8->9->10->11->12 k=4 m=3;
will result into
1->5->6->7->11->10->9->8->12
so either u should return the updated head from your function or use pointer to pointer for head
reverseLinkedList(Node n, int kc, int mc)
{
Node prev = null;
Node curr = n;
while(curr!=null)
{
int k = kc, m = mc;
while(k!=0 && curr!=null)
{
Node t = curr.next;
curr.next = prev;
prev = curr;
curr = t;
k--;
}
while(m!=0 && curr!=null)
{
curr = curr.next;m--;
}
}
}
Set a flag to do the reverse and traverse recursively
Node * rever(Node *n, int k, int m,int flag)
{
if(n==NULL)
return NULL;
if(flag==0) // do the reverse
{
Node *pre=n;
for(int i=0;i<k;i++)
{
if(pre->next !=NUL)
{
Node *tmp=pre->next;
tmp->next=pre;
pre=tmp;
}
else
{
n->next=NULL;
return pre;
}
}
flag=1;
n->next=rever(pre->next,k,m,flag);
return pre;
}
else // do the traverse
{
Node *head=n;
for(int i=0;i<m;i++)
{
if(n!=NULL)
n=n->next;
}
flag=0;
n->next=rever(n->next,k,m,flag);
return head;
}
}
#include<stdio.h>
typedef struct nod *Nodeptr;
typedef struct nod{
int data;
Nodeptr next;
} Node;
void printList(Nodeptr curr){
while(curr!=NULL)
{printf("%d\t",curr->data);
curr=curr->next;}
}
Nodeptr makeNode(int data){
Nodeptr newnodeptr = (Nodeptr)malloc(sizeof(Node));
newnodeptr->data = data;
newnodeptr->next = NULL;
return newnodeptr;
}
void kReverseList(Nodeptr *root,int k,int m){
Nodeptr prev,curr,next,prevtofirst,lastnode;
curr = *root;
prevtofirst = NULL;
int counter=0;
while(curr!=NULL){
counter=0;
prev = NULL;
lastnode=curr;
while(counter++<k&&curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
} //end of k counting
if(prevtofirst == NULL)
*root = prev;
else
prevtofirst->next = prev;
lastnode->next = curr;
counter =0;
while(counter++<m&&curr!=NULL){
prev = curr;
curr=curr->next;
} //end of m counting
prevtofirst = prev;
}
}
int main(){
Nodeptr root = makeNode(10);
Nodeptr x1 = makeNode(20);
Nodeptr x2 = makeNode(30);
Nodeptr x3 = makeNode(40);
Nodeptr x4 = makeNode(50);
Nodeptr x5 = makeNode(60);
Nodeptr x6 = makeNode(70);
Nodeptr x7 = makeNode(80);
Nodeptr x8 = makeNode(90);
Nodeptr x9 = makeNode(100);
root->next=x1;
x1->next = x2;
x2->next = x3;
x3->next = x4;
x4->next = x5;
x5->next = x6;
x6->next = x7;
x7->next = x8;
x8->next = x9;
printList(root);
kReverseList(&root,3,2);
printList(root);
return 1;
}
let assume temp,head and ptr pointing to head of linklist
My Algo is:
void function(struct node *head)
{
while(head->next != NULL)
{
ptr = head;
head = head->next;
temp = head;
while(num != k && temp->next != NULL)//reversing till K element
{
temp = temp->next;
head->next = ptr;
ptr = head;
head = temp;
num++;
}
num = 1;
while(num != m && head->next != NULL)//traversing till m element
{
head head->next;
}
}
}
To reverse a linked list we use three pointers, and algorithm is following
Three pointers are : prev,current,next;
set prev = null;
current : head;
while(current && current->data != k)
{
next = current->right;
current->right = prev;
prev = current;
current = next;
}
save prev(as it is the head node of this linked list)
head->right = current;
then travel upto m
while(current && current->data != m)
current = current->right;
again reverse remaining linkedlist.
check if current is null or not. if not then only go next.
set prev = current;
current = current->right;
while(current)
{
next = current->right;
current->right = prev;
prev = current;
current = next;
}
return saved node.
code in java
public static LinkList.LinkListNode reverse(LinkList.LinkListNode parent,
LinkList.LinkListNode child, int k, int num){
LinkList.LinkListNode lastNode = null;
if(child == null)
return parent;
else if(num == k ) {
LinkList.LinkListNode temp = child.next;
child.next = parent;
parent.next = null;
return temp;
}
else{
lastNode = reverse(child, child.next, k, num+1);
child.next = parent;
if(num == 2){
parent.next = lastNode;
}
else
parent.next = null;
return lastNode;
}
}
public static LinkList.LinkListNode traverse(LinkList.LinkListNode node,
int m){
int count = 1;
while( m != count && node.next != null){
node = node.next;
count++;
}
return node;
}
public static void reverseAndTraverse(LinkList l, int k, int m){
LinkList.LinkListNode temp = l.getHead();
if(l == null)
return;
// set the new head
LinkList.LinkListNode temp1 = temp;
int count = 1;
while (count < k && temp1.next != null){
temp1 = temp1.next;
count++;
}
l.setHead(temp1);
while(temp != null){
temp = reverse(temp, temp.next, k, 2);
if(temp != null) {
temp = traverse(temp, m);
temp1 = temp.next;
count = 1;
while(count < k && temp1 != null){
count++;
temp1 = temp1.next;
}
LinkList.LinkListNode temp2 = temp;
temp = temp.next;
temp2.next = temp1;
}
}
}
As I understand this question.
Given a linked list - 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
Given k= 3 and m = 3
we have to reverse till k, so output will be as below:
3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7
Now we need to traverse till 'm' and do the 'repeat' -this part is unclear so I assumed as below:
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7
To do this all we need is:
struct node * KrvrseMtrvrse(struct node **head, int k, int m)
{
struct node *temp1, *rev1 , *nxt1, *temp, *rev, *rev_copy, *nxt;
*temp1 = *rev1 = *nxt1 = *temp = *rev = *rev_copy = *nxt = NULL;
/* so k is over */
while(k && (*head) && (*head)->next) {
rev = *head;
nxt = rev->next;
rev->next = temp;
temp = rev;
*head = nxt;
k--;
}
rev_copy = rev;
/* here we need to add check for if(node still exists) */
/* now m turn */
while(m && (*head) && (*head)->next) {
printf("here going\n");
rev1 = *head;
nxt1 = rev1->next;
rev1->next = temp1;
temp1 = rev1;
*head = nxt1;
m--;
}
/* going to the end of first reversed list */
while(rev_copy->next != NULL)
{
rev_copy = rev_copy->next;
}
/* joining the end with the begining of the second reversed list*/
rev_copy->next = rev1;
return rev;
}
Full code is at ideone.com/JZtSOY
void reverse (struct node **base, int k , int m)
{
struct node *start,*temp,*next,*r,*s;
int i,flag=1;
start=*base;
next=temp=start;
while(next && start)
{
next=start->link;
r=next;
s=start;
for(i=2;i<=k;i++)
{
if(next == NULL)
break;
next=next->link;
r->link=s;
s=r;
r=next;
}
start->link=next;
if(temp == *base)
*base=s;
else
temp->link=s;
for(i=1;i<=m;i++)
{
if(start == NULL)
{flag=0;break;}
start=start->link;
}
if(flag){
temp=start;
start=start->link;}
}
}
The above code works fine
e.g
Enter the no. of elements in linked list(n) and the reverse shift(k) and travel shift(m) such that [2<=k,m<=n] 26 3 5
Enter the elements : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Output
3 2 1 4 5 6 7 8 11 10 9 12 13 14 15 16 19 18 17 20 21 22 23 24 26 25
Below is Java code for it. any suggestion is appreciated.
public ListNode kReversemTravel(ListNode head, int k, int m) {
ListNode init = head;
int i = 0, j = 0, l = 0;
ListNode previous = null, nxt = null, curr = null, last = null;
while (head != null && head.next != null) {
curr = head;
last = previous;
while (head != null && i < k) {
nxt = head.next;
head.next = previous;
previous = head;
head = nxt;
i++;
}
l++;
i = 0;
curr.next = head;
if (l == 1) {
init = previous;
} else {
last.next = previous;
}
previous = head;
if (head != null) {
while (head.next != null && j < m) {
previous = head;
head = head.next;
j++;
}
j = 0;
}
}
return init;
}
#include <iostream>
using namespace std;
struct node
{
int data;
node *next;
};
struct node* newnode(int value)
{
node *n=new node;
n->data=value;
n->next=NULL;
return n;
}
void display(node *n)
{
while(n->next!=NULL)
{
cout<<n->data<<"->";
n=n->next;
}
cout<<n->data<<endl;
return;
}
node * append(node *n, node *m)
{
node *temp=n;
while(n->next!=NULL)
{
n=n->next;
}
n->next=m;
n=temp;
return n;
}
node * appendlimitednodes(node *n,node *m, int l)
{
int count=0;
node *temp=n;
while(n->next!=NULL)
{
n=n->next;
count++;
}
count=0;
while(count!=l && m!=NULL)
{
node *tempnode=new node;
tempnode->data=m->data;
tempnode->next=NULL;
n->next=tempnode;
m=m->next;
n=n->next;
count++;
}
n=temp;
return n;
}
void reverse(node *n, int k, int m)
{
int entry=1;
node * newlist=NULL;
node *final;
node *finalanswer;
int count=0;
while(n!=NULL)
{
newlist=NULL;
count=0;
while(count!=k && n!=NULL)
{
node *element=n;
n=n->next;
element->next=newlist;
newlist=element;
count++;
}
final=appendlimitednodes(newlist,n,m);
if(entry==1)
{
finalanswer=final;
}
else
{
finalanswer=append(finalanswer,final);
}
entry++;
count=0;
while(count!=m && n!=NULL)
{
n=n->next;
count++;
}
}
display(finalanswer);
return ;
}
int main()
{
node *head=newnode(3);
head->next=newnode(4);
head->next->next=newnode(5);
head->next->next->next=newnode(6);
head->next->next->next->next=newnode(7);
head->next->next->next->next->next=newnode(8);
head->next->next->next->next->next->next=newnode(9);
head->next->next->next->next->next->next->next=newnode(1);
head->next->next->next->next->next->next->next->next=newnode(12);
head->next->next->next->next->next->next->next->next->next=newnode(13);
head->next->next->next->next->next->next->next->next->next->next=newnode(14);
head->next->next->next->next->next->next->next->next->next->next->next=newnode(15);
head->next->next->next->next->next->next->next->next->next->next->next->next=newnode(16);
head->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(17);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(18);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(19);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(20);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(21);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(22);
head->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next=newnode(23);
int k=3;
int m=2;
display(head);
reverse(head,k,m);
return 0;
}
- Shashi January 25, 2013#include<stdio.h> #include<stdlib.h> struct node { int val; struct node *next; }*head; struct node* createnode(int k) { struct node *temp=malloc(sizeof(struct node)); temp->val=k; temp->next=NULL; return temp; } void printlist(struct node *h) { struct node *k=h; while(k!=NULL) { printf("%d->",k->val); k=k->next; } printf("NULL"); } void KrvrseMtrvrse(struct node *h, int k, int m) { struct node* curr=h; struct node *prev=NULL; struct node *nxt,*last,*init; int i; int c; c=0; while(curr!=NULL) { i=0; c++; last=prev; init=curr; while(i<k && curr!=NULL) { nxt=curr->next; curr->next=prev; prev=curr; curr=nxt; i++; } if(c==1) head=prev; else last->next=prev; prev=init; init->next=curr; while(curr!=NULL && i<k+m) { curr=curr->next; prev=prev->next; i++; } } } int main() { head=createnode(1); head->next=createnode(2); head->next->next=createnode(3); head->next->next->next=createnode(5); head->next->next->next->next=createnode(9); head->next->next->next->next->next=createnode(7); head->next->next->next->next->next->next=createnode(4); head->next->next->next->next->next->next->next=createnode(6); head->next->next->next->next->next->next->next->next=createnode(12); head->next->next->next->next->next->next->next->next->next=createnode(31); head->next->next->next->next->next->next->next->next->next->next=createnode(11); head->next->next->next->next->next->next->next->next->next->next->next=createnode(10); printlist(head); printf("\n"); KrvrseMtrvrse(head,3,2); printlist(head); }