Reverse a singly linked listeverse a singly linked list

//Iterative reverse 

Void ReverseList(node* head)
{
        node *temp,*current,*result;
        temp=null;
        result=null;
        current=head;
        while(current!=null)
        {
                temp=current->next;//point to next element
                current->next=result;//point current element's next to prev element
                result=current;//point prev element to current element
                current=temp;
        }
   head=result;

} 

Remove duplicates from a sorted linked list

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.


// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head) 
{
  struct node* current = head;
  if (current == NULL) return; // do nothing if the list is empty

  // Compare current node with next node
  while(current->next!=NULL)
  {
      if (current->data == current->next->data)
      {
         struct node* nextNext = current->next->next;
         free(current->next);
         current->next = nextNext;
      }
      else
      {
         current = current->next; // only advance if no deletion
      }
   }
}

Insert nodes into a linked list in a sorted fashion

The solution is to iterate down the list looking for the correct place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node.

Note that we assume the memory for the new node has already been allocated and a pointer to that memory is being passed to this function.



// Special case code for the head end
void linkedListInsertSorted(struct node** headReference, struct 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!
     struct node* current = *headReference;
     while (current->next!=NULL && current->next->data < newNode->data)
     {
        current = current->next;
     }
     newNode->next = current->next;
     current->next = newNode;
   }
}


Return the nth node from the end of a linked list

Here is a solution which is often called as the solution that uses frames.

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)


STEP 1    :   1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

STEP 2    :   1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10



Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.


STEP 3    :   1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)


So here you have!, the 6th node from the end pointed to by ptr2!


Here is some C code..


struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

Binary search on a linked list

The answer is ofcourse, you can write a C program to do this. But, the question is, do you really think it will be as efficient as a C program which does a binary search on an array?

Think hard, real hard.

Do you know what exactly makes the binary search on an array so fast and efficient? Its the ability to access any element in the array in constant time. This is what makes it so fast. You can get to the middle of the array just by saying array[middle]!. Now, can you do the same with a linked list? The answer is No. You will have to write your own, possibly inefficient algorithm to get the value of the middle node of a linked list. In a linked list, you loosse the ability to get the value of any node in a constant time.

One solution to the inefficiency of getting the middle of the linked list during a binary search is to have the first node contain one additional pointer that points to the node in the middle. Decide at the first node if you need to check the first or the second half of the linked list. Continue doing that with each half-list.

C program to free the nodes of a linked list

Before looking at the answer, try writing a simple C program (with a for loop) to do this. Quite a few people get this wrong.


This is the wrong way to do it

struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = listptr->next)
{
  free(listptr);
}


If you are thinking why the above piece of code is wrong, note that once you free the listptr node, you cannot do something like listptr = listptr->next!. Since listptr is already freed, using it to get listptr->next is illegal and can cause unpredictable results!



This is the right way to do it


struct list *listptr, *nextptr;
for(listptr = head; listptr != NULL; listptr = nextptr)
{
  nextptr = listptr->next;
  free(listptr);
}
head = NULL;


After doing this, make sure you also set the head pointer to NULL!

Copy of a linked list

Check out this C program which creates an exact copy of a linked list.


copy_linked_lists(struct node *q, struct node **s)
{
    if(q!=NULL)
    {
        *s=malloc(sizeof(struct node));
        (*s)->data=q->data;
        (*s)->link=NULL;
        copy_linked_list(q->link, &((*s)->link));
    }
}


Compare two linked lists

int compare_linked_lists(struct node *q, struct node *r)
{
    static int flag;
   
    if((q==NULL ) && (r==NULL))
    {
         flag=1;
    }
    else
    {
        if(q==NULL || r==NULL)
        {
            flag=0;
        }
        if(q->data!=r->data)
        {
            flag=0;
        }
        else
        {
           compare_linked_lists(q->link,r->link);
        }
    }
    return(flag);
}


Middle of a linked list

Method1 (Uses one slow pointer and one fast pointer)
// The slow pointer is advanced only by one node
// and the fast pointer is advanced by two nodes!



typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;



void getTheMiddle(mynode *head)
{
  mynode *p = head;
  mynode *q = head;

  if(q!=NULL)
  {
       while((q->next)!=NULL && (q->next->next)!=NULL)
       {
          p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
       }
       printf("The middle element is [%d]",p->value);
  }
}









Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.

Method2(Uses a counter)

Function CAll
   middle = getTheMiddle(head);
Function definition

// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
  mynode *middle = (mynode *)NULL;
  int i;

  for(i=1; head!=(mynode *)NULL; head=head->next,i++)
  {
     if(i==1)
        middle=head;
     else if ((i%2)==1)
        middle=middle->next;
   }
 
   return middle;
}


Basic functions of link list - Add and print

// Function to add new nodes to the linked list
void add(node * head , int value)
{
   temp = (mynode *) malloc(sizeof(struct node));
   temp->next=(mynode *)0;
   temp->value=value;

   if(head==(mynode *)0)
   {
      head=temp;
      tail=temp;
   }
   else
   {
     tail->next=temp;
     tail=temp;
   }
}

// Function to print the linked list...
void print_list(struct node *head)
{
  mynode *temp;

  printf("\n[%s] -> ", listName);
  for(temp=head;temp!=NULL;temp=temp->next)
  {
    printf("[%d]->",temp->value);
  }

  printf("NULL\n");

}

Detecting a loop in a linked list (C program)

Brute force method

Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.


typedef struct node
{
  void *data;
  struct node *next;
}mynode;


mynode * find_loop(NODE * head)
{
  mynode *current = head;

  while(current->next != NULL)
  {
    mynode *temp = head;
    while(temp->next != NULL && temp != current)
    {
      if(current->next == temp)
      {
        printf("\nFound a loop.");
        return current;
      }
      temp = temp->next;
    }
    current = current->next;
  }
  return NULL;
}



Visited flag

Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method

Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code


p=head;
q=head->next;

while(p!=NULL && q!=NULL)
{
  if(p==q)
  {
    //Loop detected!
    exit(0);
  }
  p=p->next;
  q=(q->next)?(q->next->next):q->next;
}

// No loop.


To add two long positive numbers (each represented by linked lists in C)

node *long_add(mynode *h1, mynode *h2, mynode *h3)    //h3 = h2+h1
{
  node *c, *c1, *c2;
  int sum, carry, digit;

  carry = 0;
  c1 = h1->next;
  c2 = h2->next;

  while(c1 != h1 && c2 != h2)
  {
     sum   = c1->value + c2->value + carry;
     digit = sum % 10;
     carry = sum / 10;

     h3 = insertNode(digit, h3);

     c1 = c1->next;
     c2 = c2->next;
  }

  if(c1 != h1)
  {
     c = c1;
     h = h1;
  }
  else
  {
     c = c2;
     h = h2;
  }

  while(c != h)
  {
    sum   = c->value + carry;
    digit = sum % 10;
    carry = sum / 10;
    h3 = insertNode(digit, h3);
    c = c->next;
  }

  if(carry==1)
  {
     h3 = insertNode(carry, h3);
  }

  return(h3);
}

Deleting a node from a sorted link list

As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There's a tricky case where the node after the next node needs to be noted before the deletion.


// Remove duplicates from a sorted list
void RemoveDuplicates(struct node* head)
{
struct node* current = head;
if (current == NULL) return; // do nothing if the list is empty

// Compare current node with next node
while(current->next!=NULL)
{
if (current->data == current->next->data)
{
struct node* nextNext = current->next->next;
free(current->next);
current->next = nextNext;
}
else
{
current = current->next; // only advance if no deletion
}
}
}