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));
    }
}