Data structures

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are...

Sorting a linked list is much more complex than sorting an array. Because you need to be wary of links at each step and update them. The most convenient ways of sorting a linked list is insertion sort, where in you remove one node at a time from list and insert them to the sorted list in correct position. But merge sorting a linked list uses another approach. It splits the list into two halves, sorts them recursively and then merges them maintaining ascending order of key values. So the three basic parts of this approach are Splitting the list into two halves of equal length Sorting these halves Merging the halves Step 2 is in fact not needed if the list has only one node. One node is sorted. Hence the merge sort algorithm is If the list has more than one node Splitting the list into two halves of equal length Sorting these halves recursively using steps 2 to 4 Merging the halves   Split the list into halves We have seen in this post how to find the m...

Now let us write a function to count the number of nodes in a singly linked list. This one is pretty simple. traverse the list from first node increment count after each node count at the end of traversal is the number of nodes int get_count (NODEPTR temp) { int c = 0 ; while (temp) { c ++ ; temp = temp -> next; } return c; } The function starts with head node and loops till temp becomes NULL. Please remember that NULL has a numerical value of 0 and 0 is false and the condition ( temp ) is as good as saying ( temp!=NULL ). How about a recursive function for the same? int get_count_recursive (NODEPTR temp) { if (temp != NULL ) { return get_count_recursive(temp -> next) +1 ; } } Time to write the driver program for this function #include<stdio.h> #include<stdlib.h> struct node { int n; struct node * next; }; typedef struct node * NODEPTR; NODEPTR...

One of the commonly used interview question is - how do you reverse a linked list? If you talk about a recursive function to print the list in reverse order, you are so wrong. The question is to reverse the nodes of list. Not print the nodes in reverse order. So how do you go about reversing the nodes. You need to take each node and link it to previous node. But a singly linked list does not have previous pointer. So if n1 is current node, n2 = n1->next, you should set     n2->next = NULL But doing this would cut off the list at n2. So the solution is recursion. That is to reverse n nodes  n1,n2,n3... of a list, reverse the sub list from n2,n3,n4.... link n2->next to n1 set n1->next to NULL The last step is necessary because, once we reverse the list, first node must become last node and should be pointing to NULL. But now the difficulty is regarding the head? Where is head and how do we set it? Once we reach end of list  viz n1->next ==NULL, th...