Microsoft Interview Question Software Engineer in Tests Software Engineer / Developers
0of 0 votesWrite code to reverse a singly linked list
Well the solution to this problem would be to take three pointers pointing to first, second and third... make the second pointer next to point to first and first would be second, second would be third and third would be third next.. do check for end condition and case where the list is null, one element and two elements ..
node* reverse(node* head)
{
node* next;
node* prev=NULL;
node* curr=head;
if(!head) return head;
while(curr->next != NULL)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
// This is required else the last node pointer is left dangling.
curr->next=prev;
return curr;
}
I always see verbose solutions with three pointers... where does it come from?
N* reverse(N* head)
{
N* prev = NULL;
while(head)
{
N* next = head->next; // 1st store it
head->next = prev; // then change it
prev = head;
head = next;
}
return prev;
}
/*Write code to reverse a singly linked list*/
#include<stdlib.h>
#include<stdio.h>
struct NODE{
int data;
struct NODE* next;
};
typedef struct NODE* node;
node getNode(){
node x;
x=(node)malloc(sizeof(struct NODE));
return x;
}
node createList(node head,int data){
node temp,cur;
if(!head){
head=getNode();
head->data=0;
head->next=NULL;
}
cur=head;
while(cur->next){
cur=cur->next;
}
temp=getNode();
temp->data=data;
temp->next=NULL;
cur->next=temp;
return head;
}
node reverseList(node head){
node cur,next,prev;
prev=NULL;
cur=head;
next=cur->next;
while(cur->next){
cur->next=prev;
prev=cur;
cur=next;
next=next->next;
}
head=prev;
return head;
}
void display(node head){
node cur;
if(!head){
printf("\nEmpty list");
return;
}
cur=head;
printf("\n");
while(cur->next){
printf("%d ",cur->data);
cur=cur->next;
}
printf("\n\n");
}
int main(){
int i;
node head;
head=NULL;
for(i=1;i<10;i++)
head=createList(head,i);
printf("\nThe original list is :\n");
display(head);
printf("\nThe reversed list is :\n");
head=reverseList(head);
display(head);
return(0);
}
/*
The original list is :
0 1 2 3 4 5 6 7 8
The reversed list is :
8 7 6 5 4 3 2 1
Press any key to continue . . .*/
ListNode* ReverseRecursively(ListNode* listHead) {
...static ListNode* tail = NULL;
...if (tail == NULL) {
......tail = listHead->Next;
......listHead->Next = NULL;
...}
...ListNode* tmp = tail->Next;
...tail->Next = listHead;
...listHead = tail;
...tail = tmp;
...if (tail == NULL) {
......return listHead;
...}
...else {
......return ReverseRecursively(listHead);
...}
}
similar to rajnesh solution
struct Node * reverseList(struct Node * head) {
struct Node * curNode = head ;
struct Node * nextNode = NULL ;
if ((curNode==NULL)||(curNode->next==NULL)){
return head ;
}
nextNode = reverseList(curNode->next) ;
curNode->next->next = curNode ;
curNode->next = NULL ;
return nextNode;
}
similar to rajnesh solution
struct Node * reverseList(struct Node * head) {
struct Node * curNode = head ;
struct Node * nextNode = NULL ;
if ((curNode==NULL)||(curNode->next==NULL)){
return head ;
}
nextNode = reverseList(curNode->next) ;
curNode->next->next = curNode ;
curNode->next = NULL ;
return nextNode;
}
node* reverse(node *ptr)
- Samartha July 22, 2008{
if(ptr->next==NULL){head=ptr; return prt;}
reverse(node->next)->next=ptr;
}