Given a singly linked list, determine whether it contains a loop or not.

1. Start reversing the list. If you reach the head, then there is a loop.
But this changes the list. So, reverse the list again.
2. Second solution is called Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment first pointer by one and
second pointer by 2. After each increment comapre if they are equal. They will meet if there is a loop.

p1 = p2 = head;
do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);

3. Hash all seen nodes and compare the next node with the nodes in the hash. If a node is already present in the hash then there is a loop.

Under what circumstances can one delete an element from a singly linked list in constant time?

If the list is circular and there are no references to the nodes in the list from anywhere else! Just copy the contents of the next node and delete the next node. If the list is not circular, we can delete any but the last node using this idea. In that case, mark the last node as dummy!

Remove duplicates from a linked list ?

NODE *DupRem(NODE *head)
{
NODE *p1 = head, *p2, *resultList = NULL, *temp = NULL;
while(p1 != NULL)
{
p2 = p1->link;
while(p2 != NULL)
{
if(p1->data == p2->data)
{
break;
}

else
{
p2 = p2->link;
}
}

if(p1->data==p2->data)
{
p1 = p1->link;
}else
{
if(resultList == NULL)
{
resultList = p1;
temp = p1;
p1 = p1->link;
}else
{
temp->link = p1;
temp = temp->link;
p1 = p1->link;
}
}
}
return resultList;
}

Given two sorted linked lists, write a function to merge them into one?

list* merge(LIST* list1, LIST* list2){
LIST *it1, *it2, *head;
if(!list1) return list2;
if(!list2) return list1;
head = (list1->value <= list2->value) ? list1 : list2;
if(head == list1)
{ it1 = list1; it2 = list2;
}
else{
it1 = list2;
it2 = list1;
}
while(it1->next && it2){
if(it1->next->value >= it2->value){
list *temp = it1->next;
it1->next = it2;
it2 = it2->next;
it1->next->next = temp;
}
else{
it1 = it1->next;
}
}

if(it2)
it1->next = it2;
return head;
}

Given a single linked list write a function to swap each pair of nodes by manipulating with pointers (not values).?

Sol:
Original list: head->1->2->3->4->5->NIL should be transformed to head->2->1->4->3->5-> NIL

int reverse_pairs(LLIST ** head)
{
LLIST * temp = ULL;
LLIST* current_pair = *head;
LLIST** previouspair = head;
while((current_pair != NULL) && (current_pair->next != NULL))
{
temp = current_pair;
current_pair = current_pair->next;
temp->next = current_pair->next;
current_pair->next = temp;
*previouspair = current_pair;
current_pair = temp->next;
previouspair = &temp->next;
}
return 0;
}