Q1) how do you reverse a single linked list.
a) there are num of ways to do this. 1 way is just keep on iterating through linked list and add those nodes at head of new linked list
pseudo code is here
node* reverse(node *elem)
{
if (elem == NULL) return NULL;
if (elem->next == NULL) return elem ;
node *n1 = reverse(elem->next);
if(n1 != NULL)
n1->next = elem;
return n1;
}
alternative way is reversing pointers in place
Node* reverse(Node* root) {
Node* new_root = 0;
while (root) {
Node* next = root->next;
root->next = new_root;
new_root = root;
root = next;
}
return new_root;
}
Q2) deleting a node in single Linked list
A)
Node deleteNode(Node head, int d) {
Node n = head;
if (n.data == d) {
return head.next; /* moved head */
}
while (n.next != null) {
if (n.next.data == d) {
n.next = n.next.next;
return head; //just return head
}
n = n.next;
} //end while
}
Q3) get last n nodes in single linked list of unknown length
A) In single list list, we can only go fwd direction. so how do we get last n nodes, if we don't know the length of linked list .
approach 1: when we keep traversing the list, store the nodes in stack. when we reach end of linked list, pop up the stack 'n' times. but we are going to waste the space as we are storing all linked list nodes in stack. space complexity is O(n) . so what can we do about saving the space in stack?. we can store the nodes in Queue now when we traverse the linked list , when ever the Queue length crosses the 'n' we remove the elements in Q, so that at instance we have 'n' nodes in Q.
approach 2 :
have 2 pointers which point to head of linked list say p1 and p2 . iterate p1 to 'n' positions from head pointer. then again iterate p1 and p2 together, until p1 reaches the end of linked list. now the positions of p1 and p2 will differ by n positions . the position of p2 will be at n positions from end .
as the approach 2 has less space complexity, I am going to give pseudo code for approach 2 :
pseudo code:
node GetLast_Nelements(node head, int n )
{
if (head==NULL)
return NULL
p1=p2=head
for(i=0; i < n ; i=i+1)
{
if(p1 ==NULL)
return head ; //linked list doesnt have 'n' elements at all
p1=p1->next
}
while (p1 !=NULL)
{
p1=p1->next;
p2=p2->next ;
}
return p1 ;
}
Q) swap elements in linked list
input list : 1->2->3->4->5->6
output list: 2->1->4->3->6->5
A)
node * shuffle (node *&head)
{
if(head == NULL)
return head ;
if (head->next ==NULL)
return head;
node *firstnode=head;
node *secondnode=firstnode->next;
firstnode->next=firstnode->next->next ;
secondnode->next=firstnode;
head=secondnode ;
node *prev=firstnode;
firstnode=firstnode->next;
node *temp=NULL,*next=NULL,*curr=NULL;
while(firstnode !=NULL && firstnode->next!=NULL)
{
curr=firstnode;
temp=firstnode->next;
firstnode->next=firstnode->next->next;
prev->next=temp;
temp->next=curr;
prev=curr;
firstnode=firstnode->next;
}
prev->next=firstnode;
prev=firstnode;
return head ;
}
Q) merge linked lists in sorted way
say we have 2 sorted linked lists to merge n1 and n2 . Then pass head element of n1 , every element of n2 to the linkedListInsertSorted .
void linkedListInsertSorted( node** headReference, node* newNode)
{
// Special case for the head end
if (*headReference == NULL || (*headReference)->data >= newNode->data)
{
newNode->next = *headReference;
*headReference = newNode;
}
else {
// Locate the node before which the insertion is to happen!
node* current = *headReference;
while (current->next!=NULL && current->next->data < newNode->data)
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}//end else
} // end func
