Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
yes you are right...here is the same implemented in c++
node* appendLastNtoBegin(node* head,int n){
if ((!head) || (!head->next) || n<=0)
return head;
node * curr(head),*curr2(head), *prev(NULL);
int i(1);
while(curr->next){
if (i<n) i++;
else{
prev= curr2;
curr2= curr2->next;
}
curr=curr->next;
}
if (i<n){
cout<<"invalid input for N"<<endl;
return head;
}
prev->next=NULL;
curr->next=head;
head=curr2;
return head;
}
@ankit thanks for pointing that out... I can do away with curr2 by using prev or vice-versa
node* appendLastNtoBegin(node* head,int n){
if ((!head) || (!head->next) || n<=0)
return head;
node * curr(head), *prev(head);
int i(1);
while(curr->next){
if (i<n) i++;
else prev = prev->next;
curr=curr->next;
}
if (i<n){
cout<<"invalid input for N"<<endl;
return head;
}
prev->next=NULL;
curr->next=head;
head=prev;
return head;
}
node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr->next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr->next != NULL) {
curr = curr->next;
prev = prev->next;
}
curr->next = root;
root = prev->next;
prev->next = NULL;
return root;
}
some correction is
node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr->next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr->next != NULL) {
curr = curr->next;
prev = prev->next;
}
prev = prev->next;(add this now yr code will work)
curr->next = root;
root = prev->next;
prev->next = NULL;
return root;
}
- hi ,, to find nth node yr while loop should be while(cur!=NULL) not this one while (curr->next != NULL)
some correction is
node *prepend(node * root, int k)
{
node *prev, *curr;
curr = root;
for (int i = 0; i < k; i++) {
curr = curr->next;
if (curr == NULL)
return NULL;
}
prev = root;
while (curr->next != NULL) {
curr = curr->next;
prev = prev->next;
}
prev = prev->next;(add this now yr code will work)
curr->next = root;
root = prev->next;
prev->next = NULL;
return root;
}
struct Node *ListArrange(struct Node *node,int n)
{
if(!node || n==0)
return node;
struct Node *head=node;
struct Node *first=node,*second=node;
int count=n;
while(first && count--)
first=first->next;
while(first && first->next)
{
first=first->next;;
second=second->next;
}
if(!first)
return head;
struct Node *temp=second->next;
first->next=head;
second->next=NULL;
head=temp;
return head;
}
struct node* change(struct node* start,int items)
{
struct node* item = start;
struct node* st = start;
struct node* last = NULL;
int move=0;
while (start != NULL)
{
if(start->next != NULL)
{
start = start->next;
move++;
if(move > items)
{
item = item->next;
}
}
else
break;
}
struct node* temp= item->next;
item->next = NULL;
start->next = st;
return temp;
}
private static Node moveNodesToBeginning(Node root, int n) {
Node current = root;
Node slowCurrent = root;
while(current.next != null){
if(n<=0)
slowCurrent = slowCurrent.next;
current = current.next;
n--;
}
if(n>0){
current.next = root;
root = slowCurrent.next;
slowCurrent.next = null;
}
return root;
}
public LinkedListNode appendNodes(LinkedListNode root, int k) {
int nodeCount = 0;
LinkedListNode temp = root;
LinkedListNode lastNode = null;
while (temp != null) {
nodeCount++;
lastNode = temp;
temp = temp.getNext();
}
temp = root;
System.out.println(lastNode.getValue());
while ((nodeCount - k) != 1) {
temp = temp.getNext();
nodeCount--;
}
lastNode.setNext(root);
root = temp.getNext();
temp.setNext(null);
return root;
}
I think this solution is correct. Please test it.
public class AppendLinkedList {
int size;
Node head;
Node tail;
class Node {
int value;
Node next;
public Node(int value) {
super();
this.value = value;
this.next = null;
}
}
public void add(int value) {
Node n = new Node(value);
if (head == null) {
head = n;
tail = n;
}
tail.next = n;
tail = n;
size++;
}
public void append(int n) {
if (n > size || n < 0) {
System.out.println("n is out of range!");
return;
}
Node ptr = head;
int index = size - n - 1;
if(index == -1){
return;
}
while (index > 0) {
ptr = ptr.next;
index--;
}
tail.next = head;
head = ptr.next;
tail = ptr;
ptr.next = null;
}
public void print() {
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.value + "\t");
ptr = ptr.next;
}
System.out.println();
}
public static void main(String[] args) {
AppendLinkedList l = new AppendLinkedList();
l.add(1);
l.add(2);
l.add(3);
l.add(4);
l.add(5);
l.add(6);
l.print();
l.append(0);
l.print();
}
}
This is using the standard Tortoise & Hare approach.
private void appendLast(int n){
//Declare a slow and a fast pointer.
LinkListNode slow = head;
LinkListNode fast = head;
//If no number is passed.
if(n==0) return;
else{
//Take the fast pointer to nth node from the last.
while(n>0 && fast.next!=null){
fast = fast.next;
--n;
}
//If the number of nodes are less than the given number n.
if(fast.next==null && n!=0){
System.out.println("Cannot be done!.");
return;
}else{
//Move the fast and the slow pointer.
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
//Make the switch.
fast.next = head;
head = slow.next;
slow.next = null;
}
}
}
public void appendrearTofront(int n)
{
Node2 slowpointer,fastpointer;
slowpointer=front;
fastpointer=front;
while(fastpointer!=null)
{
while((n+1)!=0)
{
fastpointer=fastpointer.nextlink;
n--;
}
fastpointer=fastpointer.nextlink;
slowpointer=slowpointer.nextlink;
}
rear.nextlink=front;
front=slowpointer.nextlink;
slowpointer.nextlink=null;
slowpointer=rear;
}
public void AppandLastnNode(Node head, int n)
{
if (n<= 0 ) return;
if (head == null) return;
if (head.next == null) return;
Node tmp1 = new Node();
Node tmp2 = new Node();
tmp1 = tmp2 = head ;
for (int i = 1 ; i <= n ; i++)
{
tmp2 = tmp2.next;
}
while (tmp2.next != null)
{
tmp1 = tmp1 .next;
tmp2 = tmp2. next;
}
tmp2.next = head;
head = tmp1.next;
tmp1.next = null;
}
void AppendNthElementsFromEndToStart(stIntList* pRoot,stIntList*& pNew, int n)
{
if(NULL == pRoot)
return;
stIntList* pCurr = NULL;
stIntList* pKthElem = pRoot;
stIntList* pPrev = NULL;
stIntList* pCurPrev = NULL;
int count = 1;
while(pKthElem != NULL)
{
pPrev = pKthElem;
pCurPrev = pCurr;
if(count < n)
{
if(NULL == pKthElem)
break;
pKthElem = pKthElem->pNList;
count++;
continue;
}
if(count == n)
{
pCurr = pRoot;
pKthElem = pKthElem->pNList;
count++;
continue;
}
pCurr = pCurr->pNList;
pKthElem = pKthElem->pNList;
}
//Now Current Node is the Nth node from reverse.
pCurPrev->pNList = NULL;
pNew = pCurr;
pPrev->pNList = pRoot;
}
void Ques(int k)
{
//First,count the number of the elements in the linked list
temp=p;
prev=p;
int n=0;
while(temp!=NULL)
{
n++;
temp=temp->link;
}
temp=p;
int i;
for(i=0;i<n-k;i++)
{
temp=temp->link;
if(i!=0)
{//here prev has been pointing to one node before the
//temp since it is stopped once by putting the if condition.
prev=prev->link;
}
}
prev->link=NULL;
//now the complete chain will be appended to the start of the original
xy=temp;
for(int j=i;j<n-1;j++)
{
temp=temp->link;
}
temp->link=p;
p=xy;
}
}
void swap_nth(node*& head, int n)
{
if(head == NULL) return;
node* second = head;
for(int i = 0; i < n - 1; ++i)
{
if(second->next == NULL) //still in loop and haven't iterated n-1 places
{
return;
}
second = second->next;
}
node* first = head;
while(second->next != NULL)
{
second = second->next;
first = first->next;
}
//now swap
first->next = NULL;
second->next = head;
}
import java.util.Scanner;
class Node
{
int data;
Node next;
}
public class LinkList
{
Node start=null;
void addLast(int data)
{
Node n1=new Node();
n1.data=data;
n1.next=null;
if(start==null)
{
start=n1;
}
else
{
Node temp1=start;
while(temp1.next!=null)
{
temp1=temp1.next;
}
temp1.next=n1;
}
}
void printList()
{
int count=0;
Node temp2=start;
while(temp2!=null)
{
System.out.println(temp2.data);
temp2=temp2.next;
count++;
}
System.out.println("total no of node:"+count);
}
void append()
{
int c=0;
Node temp3=start;
while(temp3!=null)
{
temp3=temp3.next;
c++;//no of node count.
}
Scanner s=new Scanner(System.in);
System.out.println("how many node u want 2 append");
int n=s.nextInt();
Node temp5=start;
int i;
for(i=1;i<=c-n;i++)
{
temp5=temp5.next;
}
while(i<=c)//first print that node u append.
{
System.out.println(temp5.data);
temp5=temp5.next;
i++;
}
int p=c-n;
Node temp4=start;
for( i=1;i<p;i++)
{
temp4=temp4.next;
}
temp4.next=null;//delete that node u appended above.
}
public static void main(String[] args)
{
LinkList l=new LinkList();
l.addLast(50);
l.addLast(60);
l.addLast(70);
l.addLast(80);
l.addLast(45);
l.printList();
l.append();
l.printList();
}
}
void append()
{
int c=0;
Node temp3=start;
while(temp3!=null)
{
temp3=temp3.next;
c++;
}
Scanner s=new Scanner(System.in);
System.out.println("how many node u want 2 append");
int n=s.nextInt();
Node temp5=start;
int i;
for(i=1;i<=c-n;i++)
{
temp5=temp5.next;
}
while(i<=c)//first print that node u append.
{
System.out.println(temp5.data);
temp5=temp5.next;
i++;
}
int p=c-n;
Node temp4=start;
for( i=1;i<p;i++)
{
temp4=temp4.next;
}
temp4.next=null;//delete that node u appended above.
}
void LinkedList::Prepend(int n)
{
Node* fast = new Node;
fast = this->list;
Node* slow = new Node;
slow = this->list;
int delta = n;
while(delta >0)
{
fast = fast->next;
delta = delta-1;
}
delta = n-delta;
while(fast->next != NULL)
{
slow = slow->next;
fast = fast->next;
}
//slow points the target node now, point it to the start
fast->next = this->list;
this->list = slow->next;
slow->next = NULL;
}
here is how I implemented this:
bool LinkedList::Prepend(int count)
{
if(0 >= count || NULL == this->m_Start)
{
return false; // nothing to do...
}
Node* fast = this->m_Start;
for(int index = 0; index < count; index++)
{
fast = fast->m_Next;
if(NULL == fast)
{
return false; // can't be done...
}
}
if(NULL == fast->m_Next)
{
return false;
}
Node* slow = this->m_Start;
while(NULL != fast->m_Next)
{
fast = fast->m_Next;
slow = slow->m_Next;
}
fast->m_Next = this->m_Start;
this->m_Start = slow->m_Next;
slow->m_Next = NULL;
return true;
}
private void appendLastNodesToStartOfList(LinkedList<Integer> linkedList, int noOfNodesToAppend){
LinkedListNode<Integer> lowerPtr = linkedList.getFirstLinkedListNode();
LinkedListNode<Integer>higherPtr = linkedList.getFirstLinkedListNode();
for(int i=0;i<noOfNodesToAppend; i++){
higherPtr = higherPtr.getNextNode();
}
while(higherPtr.getNextNode() != null){
lowerPtr = lowerPtr.getNextNode();
higherPtr = higherPtr.getNextNode();
}
LinkedListNode<Integer> tempNode = lowerPtr.getNextNode();
lowerPtr.setNextNode(null);
higherPtr.setNextNode(linkedList.getFirstLinkedListNode());
linkedList.setFirstLinkedListNode(tempNode);
}
public class appendLastNNodeToHead extends LinkedList{
public Node appendLastNNodes(Node head,int k){
int size = this.getSize();
if(k==0 || k==size){
return head;
}
Node end = this.getNodeAtIndex(size-k-1);
Node newHead = end.next;
Node fast = newHead;
while(fast.next !=null){
fast = fast.next;
}
end.next = null;
fast.next = head;
head = newHead;
return head;
}
public static void main (String[] args){
appendLastNNodeToHead l = new appendLastNNodeToHead();
l.add(0,10);
l.add(1,12);
l.add(2,2);
l.add(3,3);
l.add(4,34);
System.out.println("After addition");
l.display();
Node head = l.getHead();
int k = 4;
Node head2= l.appendLastNNodes(head,k);
l.displayLL(head2);
}
}
public class appendLastNNodeToHead extends LinkedList{
public Node appendLastNNodes(Node head,int k){
int size = this.getSize();
if(k==0 || k==size){
return head;
}
Node end = this.getNodeAtIndex(size-k-1);
Node newHead = end.next;
Node fast = newHead;
while(fast.next !=null){
fast = fast.next;
}
end.next = null;
fast.next = head;
head = newHead;
return head;
}
public static void main (String[] args){
appendLastNNodeToHead l = new appendLastNNodeToHead();
l.add(0,10);
l.add(1,12);
l.add(2,2);
l.add(3,3);
l.add(4,34);
System.out.println("After addition");
l.display();
Node head = l.getHead();
int k = 4;
Node head2= l.appendLastNNodes(head,k);
l.displayLL(head2);
}
}
sample testcases :
k =0
i/p: 10 12 2 3 34
o/p; 10 12 2 3 34
------------------------------------
k= 1
i/p: 10 12 2 3 34
o/p: 34 10 12 2 3
----------------------------------
k=2;
i/p: 10 12 2 3 34
o/p: 3 34 10 12 2
-----------------------------------------
k= 3
i/p: 10 12 2 3 34
o/p: 2 3 34 10 12
------------------------------------------
k =4 ;
i/p : 10 12 2 3 34
o/p: 12 2 3 34 10
------------------------------------------
k = 5
i/p: 10 12 2 3 34
o/p: 10 12 2 3 34
Easy:
void AddNodes(PSList *ppHead, size_t N)
{
PSList current = NULL;
PSList faster = NULL;
if (ppHead && *ppHead && N)
{
current = *ppHead;
faster = *ppHead;
while (N > 0 && faster)
{
faster = faster->Next;
N--;
}
if (faster)
{
while (faster->Next)
{
current = current->Next;
faster = faster->Next;
}
// adjust head
faster->Next = *ppHead;
*ppHead = current->Next;
current->Next = NULL;
}
}
}
/**
*
*/
package com.singlelinkedlist;
/**
* @author mohammed.anas
*
*/
public class SingleNode {
String data;
SingleNode nextnode;
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public SingleNode getNextnode() {
return nextnode;
}
public void setNextnode(SingleNode nextnode) {
this.nextnode = nextnode;
}
public SingleNode(String data){
this.data=data;
this.nextnode=null;
}
}
******************************************
/**
*
*/
package com.singlelinkedlist;
/**
* @author mohammed.anas
*
*/
public class SingleLinkedList {
/**
* @param args
*/
private SingleNode start;
private SingleNode end;
public SingleLinkedList(){
this.start=null;
this.end=null;
}
private void insert(String data){
if(start==null){
start=new SingleNode(data);
end=start;
}
else{
end.nextnode=new SingleNode(data);
end=end.nextnode;
}
}
private void delete(String data){
SingleNode next=start.nextnode;
SingleNode prev=start;
if(data==start.getData()){
start=start.nextnode;
}
else{
while(next.getData()!=data){
next=next.nextnode;
prev=prev.nextnode;
}
if(next==end){
prev.nextnode=null;
end=prev;
}
else{
prev.nextnode=next.nextnode;
}}
}
private void display(){
SingleNode temp=start;
while(temp!=null){
System.out.println(temp.getData());
temp=temp.nextnode;
}
}
private int count(){
int count=0;
SingleNode temp=start;
while(temp!=null){
temp=temp.nextnode;
++count;
}
return count;
}
private void lasttobeginning(int num){
SingleNode temp=start;
SingleNode result=null;
SingleNode temp2=null;
int count=count();
for (int i = 1; i <count-num; i++) {
temp=temp.nextnode;
}
result=temp.nextnode;
temp2=result;
temp.nextnode=null;
while(result.nextnode!=null){
result=result.nextnode;
}
result.nextnode=start;
start=temp2;
}
public static void main(String[] args) {
SingleLinkedList singleLinkedList=new SingleLinkedList();
singleLinkedList.insert("Germany");
singleLinkedList.insert("Poland");
singleLinkedList.insert("Russia");
singleLinkedList.insert("Japan");
singleLinkedList.insert("Turkey");
singleLinkedList.insert("Protugal");
singleLinkedList.insert("Croatia");
singleLinkedList.display();
singleLinkedList.lasttobeginning(3);
System.out.println("***************************");
singleLinkedList.display();
}
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int create();
void append(int p,int q);
void display();
struct list
{
int data;
struct list*link;
};
typedef struct list node;
node *s,*head,*head1,*temp,*temp1,*st,*prev,*next;
void main()
{
int n,l;
clrscr();
s=(node*)malloc(sizeof(node));
head=st=s;
l=create();
printf("enter how many nodes do you want to append from end");
scanf("%d",&n);
append(l,n);
display();
getch();
}
int create()
{
int c,len=0;
while(c)
{
len++;
printf("enter element");
scanf("%d",&s->data);
printf("do you want to enter another one yes-1/no-0:");
scanf("%d",&c);
if(c==0)
{
s->link=NULL;
break;
}
else
{
s->link=(node*)malloc(sizeof(node));
s=s->link;
}
}
return len;
}
void append(int p,int q)
{
int r,len=0,k;
r=p-q; k=q-1;
while(head!=NULL)
{
len++;
if(len==r)
{
temp=head->link;
head->link=NULL;
}
head=head->link;
}
prev=head1=temp;
temp1=head1;
while(k!=0)
{
next=temp1->link;
if(k==1)
next->link=st;
temp1=next;
k--;
}
}
void display()
{
while(head1!=NULL)
{
printf("%d->",head1->data);
head1=head1->link;
}
printf("NULL");
}
public void append(int idx) {
circular();
IntNode newNode = head;
for (int i = 0; i < getNodeCount() - idx; i++) {
newNode = newNode.next;
}
IntNode temp = newNode.next;
newNode.next = null;
head.next = temp;
}
public void circular(){
IntNode currentNode = head;
while (null != currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = head.next;
}
This is my java solution with a time complexity of O(n) :
class Nodeapp{
Nodeapp next;
int data;
Nodeapp(int x){
data=x;
}
}
public class NodeAppendN {
Nodeapp root;
public void print(){
Nodeapp temp =root;
if(temp==null)
return;
while(temp!=null){
System.out.print(temp.data+" ");
temp=temp.next;
}
}
public void append(int n){
Nodeapp fast=root, slow=root;
Nodeapp temp=root;
for(int i=0;i<n;i++){
fast=fast.next;
}
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
}
Nodeapp jk=slow.next;
slow.next=null;
fast.next=temp;
root=jk;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
NodeAppendN link =new NodeAppendN();
link.root=new Nodeapp(1);
link.root.next=new Nodeapp(2);
link.root.next.next=new Nodeapp(3);
link.root.next.next.next=new Nodeapp(4);
link.root.next.next.next.next=new Nodeapp(5);
link.print();
link.append(2);
System.out.println("Appended list is");
link.print();
}
}
start traversing till you traverse n elements.
- Anonymous February 07, 2013start another traverse in same loop after meeting above condition
(there will be always gap of n nodes between these to pointers )
when first pointer reach to end of linked list second pointer will be n node behind.
just change the pointer .