Merging two sorted linked list

Question : Given two sorted linked lists,How to manage them into the third list in sorted order

Pseudo code :  These problem can be resolved with both an iterative method as well as recursive method. Through out my experience I always find solution with recursive difficult to understand so I will try and explain recursive method in better way.

Code :
struct node* Merge_list( struct node *a,struct node *b)
{
struct node *result = NULL;
if(a == NULL)
       {
 return b;
       }
if(b == NULL)
{
         return a;
        }

if(a->data <= b->data)
{
result = a;
result->link = Merge_list(a->link,b);
}
else
{
result = b;
result->link = Merge_list(a,b->link);
}

return result;
}

Understanding :  By seeing above code I know most of the people find it difficult to understand.But if you try to understand solution with diagram it is not much difficult also.

Ex:

Sorted Link list elements of a : 1 -> 3 ->7
Sorted Link list elements of b : 2 -> 4 ->5

For sake simplicity as per below diagram I have assigned static address.If you follow below two diagrams carefully you will notice that how final result holds the end result.

Result linked list is : 1 -> 2 -> 3 -> 4 ->5 ->7

Static Link List Node

Red line of code shows value assigned while return from recursive call

Given kth and k+1 node find out k-1 node in singly linked list

Pseudo code:

Given kth and k+1 node address in a single linked list you have to find out previous node consider you do not have address of head node.

Detail about implementation :

By first seeing it seems impossible task but it can be easily done using property of XOR gate.

Ex.
A xor A = 0
A xor NULL = A
C=B xor D ===> C xor D will give you B.

So the idea is Create a singly linked list where next pointer is made by doing Xor operation of previous node and next node.

Linked List : a -> b -> c -> d -> e -> f

a = null xor b
b = a xor c
c = b xor d
e = d xor f
f = e xor null

Steps :

1) If linked address of node b and c is given in that case we can easily find address of node a by applying xor operation.

Here b = (a xor c) so we can easily get 'a' by applying xor operation with c.
(a xor c) xor c ==> a.

Display linked list from the end

Pseudo code:

1) Recursively call Display_from_end API till you get the end of the linked list.
2) Once you get the linked list print the node.

void Display_from_end(struct linkedlist *head)
{
    if(head == NULL)
    return;
   Display_from_end(head->next);
   printf("%d",head->data);

}

Ex:
Linked List L : 1 -> 2 -> 3 -> 4

Finding middle of the singly linked list

Pseudo Code :
There can be Bruit force approach applied in which first finding a length of linked list n and in second step move pointer to n/2 node which is the middle of the linked list.But there is also easier and efficient approach which is mentioned below.

Ex :
Linked List : 1 ->2 ->3 ->4 ->5 ->6 ->7
Point p1 to node 1 and p2 with node 3.
p1 :1 -> 2 ->3
p2: 3 -> 5 -> 7

Steps :
1) Have to pointers p1 and p2.
2) Move one pointer p1 with twice the number of nodes w.r.t to pointer p2.
3) By the time p1 approaches the end of the linked list p2 will point to middle node of the linked list.

Finding a merging point of two separate linked list

Pseudo code :
We can use of Hash table and array sorting method to find out the merging point but below is easier and less complex method of doing the same task.

Ex.

Linked List 1 :     l1->l2->l3->l4->->l5->m1->m2->m3 ( Length is : 8)
Linked List 2 :     k1->k2->k3->m1->m2->m3 ( Length is : 6)

As you can observe m1 node is the merging point of two linked list.

Steps:

1) Find out the length of both linked list. (In given example linked length is 8 and 6).
2) Get difference of the length and assign it to local variable d. (It is 2 (8-6) in given example )
3) Make the d steps in longer linked list.
4) Step in  both list in parallel until links to next node match.

Reversing singly linked list

Pseudo code: Iterative solution

Ex : Input List: 1->2->3->4->5->6

Head Point to : 1st Node
NextPtr Points to : 2nd Node

1) Have two pointers. (tempptr and nextptr ).
2) Initialize nextptr to next of head ptr ( nextptr points to 2 w.r.t example) and assign next of head ptr to NULL.
3) If nextptr is not NULL in that case copy next node address of nextptr into tempptr.(tempptr = nextptr->next).
4) Assign next node of nextptr as head node.(nextptr->next = head).
5) Assign nextptr as new head node.(head = nextptr).
6) Copy tempptr value in nextptr
7) Start from step 3 and if condition failed in that case new linked list form with head ptr is reverse one.

Note :

Linked list with head ptr grows as : 1 to 2>1 to 3->2-1 to 4->3->2->1 to 5->4>3>2>1 to 6->5->4->3->2->1.

Removing a loop in Singly Linked List

Pseudo code: 

1. Two pointers start from head 
2. One pointer advances one while the other advances two. 
3.1 If two pointers meet, there is a loop 
3.2 If pointer reaches the end, there is no loop 
4. Find out how many nodes in the loop, say k. 
5. Reset one pointer to the head, and the other pointer to head + k. 
6. Move both pointers at the same pace, they will meet at loop starting node 
7. Move one pointer till its next node is the loop starting node. It's the loop ending node 
8. Set the next node of the loop ending node to fix the loop 
9. Print the list