Microsoft Interview Question
Software Engineer / DevelopersTeam: STB
Country: India
Interview Type: In-Person
mynode* fun(mynode* root)
{
if(root->next!=NULL)
{
fun(root->next);
root->next->next=root;
return root;
}
else
head=node;
}
mynode is a struct type.
void toreverse1 (node *head ,node *head2 )
{
if(head2->next!=NULL)
toreverse1(head2,head2->next);
head2->next=head;
head->next=NULL;
}
node * toreverse (node *head )
{
node * q=head;
if(head==NULL)
return head;
while(q->next!=NULL)
{
q=q->next;
}
if(q==head)
return head;
toreverse1(head,head->next);
return q;
}
Well there are actually n number of ways to reverse a linked list. One way is to simply a make an empty linked list and while traveling through the nodes of the current linked list use a push function (which is used for pushing elements in stack) to push the elements in the result linked list. Here is the code.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
void push(struct node **headref, int num) {
struct node * newnode = malloc(sizeof(struct node));
newnode->data = num;
newnode->next = *headref;
*headref = newnode;
}
void reverse(struct node **headref) {
struct node *current = *headref;
struct node *result = NULL;
while(current != NULL) {
push(&result, current->data);
current = current->next;
}
*headref = result;
}
int main() {
struct node *head = NULL;
push(&head,1);
struct node *tail;
tail = head;
int i;
for(i = 2; i <= 5; i++) { //Here we are making a linked list {1,2,3,4,5} with head pointing to 1.
push(&(tail->next),i);
tail = tail->next;
}
reverse(&head);
while(head != NULL) { //After calling reverse the output will be printed as {5,4,3,2,1}.
printf("%d ", head->data);
head = head->next;
}
system("pause");
return 0;
}
Another approach is to use recursion. Well to use recursion to solve this problem is a bit tricky.
Here is the code.
void reverse(struct node **headref) {
struct node *first = *headref;
struct node *rest;
if(first == NULL) {
return;
}
rest = first->next;
if(rest == NULL) {
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}
Language: C++
Implementation:Iterative
Linked List Node: <int value, Node * next>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <cstdlib>
struct Node {
Node * next;
int value;
};
void test (Node * root);
void reverse(Node * root);
int main (int argc, char ** argv) {
//new linked list
Node * root = new Node;
root->next = NULL;
Node * current = new Node;
Node * node;
//step 1:
//set the root of the lis
current->value = 0;
current->next = NULL;
//set the beginning of the list
root->next = current;
//step 2: fill the array
for (int i=1; i<5; i++) {
node = new Node;
node->value = i;
node->next = NULL;
current->next = node;
current = current->next;
}
//display as test
test(root);
//reverse linked list
//Step 3: Reverse the list
reverse (root);
test(root);
}
//Function template @
//geeksforgeeks.org/write-a-function-to-reverse-the-nodes-of-a-linked-list/
void reverse (Node * root ) {
Node * current; //node that we need to update
Node * next; //node that 'current' points to before reverting
Node * previous; //node that 'current' needs to point to after reverting
//get first element
current = root->next;
//make sure this first element is set up to point to NULL (by making 'previous' = NULL) since it will be the last item of the array
previous = NULL;
while (current !=NULL) {
next = current->next;
current->next = previous;
previous = current;
current = next;
}
//make sure the root is pointing to the last element
//and not 'current' because at this point current = NULL
root->next = previous;
}
void test (Node * root) {
Node * node;
node = root->next;
while (node !=NULL) {
printf ("%u \n", node->value);
node = node ->next;
}
}
{{
- trekster July 09, 2012node *reverse(node *root, node *newHead)
{
if(node->next == NULL) return newHead;
node *cur = reverse(root->next, newHead);
cur->next = root;
return root;
}}
newHead is reversed list.