Linked List: Merged List Problem

Problem: There are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join.

Solution 1:

1. Find length of both linked lists, say len1 and len2.
2. Make current pointers for both lists equidistant from the common node. If one of the lists is longer we need to advance its current pointer by len1 - len2 (assuming list1 is longer). Now both current pointers should be equidistant from the common node. If both lists are same len, do nothing in step 2.
3. Traverse both lists simultaneously while comparing the current pointers for equality. At ant point if they are equal we have found the first common node. If we reach the end of the lists without find the common node then the lists do not overlap.

Solution 2 : This solution only tells if the lists are joined, not where though. Interesting technique nevertheless.

1. Update the tail of one of the lists to point to the head of the other.
2. Now use the linked list cycle/loop detection technique to find if there is a loop in the combined list.
3. If there is a loop then the list have node(s) in common, otherwise they don't.

Linked List: Reverse

Question: Given the head pointer to a singly linked list reverse the list.

Solution 1: Recursive Approach - We can recursively traverse the linked list till we arrive at the last but one node. We then set the next pointer of the last node to point to the current node. We keep reversing the links as we unwind the recursive calls.

Code:

// Takes a pointer to the head node of a singly linked list
// and returns the new head pointer for the reversed list
Node * Reverse(Node * head)
{
   Node *newHead = Recursive_Reverse(head);
   head->next = NULL;      // since the first node is the last node now
                           // we need to set it's next pointer to NULL
   return newHead;
}

Node * Recursive_Reverse(Node * node)
{
   Node *nextNode = node->next;
   if(nextNode == NULL)       // if the list has only one node
   {                          // we don't need to reverse it
       return node;
   }

   if(nextNode->next == NULL) // if nextNode is the last node we terminate the recursion
   {
       nextNode->next = node; // reverse the link
       return nextNode;       // return the ptr to the last node
                              // this will become the new head pointer
   }
   Node *head = Reverse(node->next); //recursively call Reverse
   nextNode->next = node;     // reverse the link
   return head;             
}

Solution 2: We can also reverse the singly linked list using an iterative approach. For some this approach can be easier to understand. Basically, we maintain 3 pointers (prevNode, currentNode, and nextNode). At each step we save the next of the currentNode in the nextNode ptr and reverse the link. After this, we advance the previous and current pointers.

Code:

//Takes a pointer to the head of a linked list
//Returns the pointer to the new head (old tail) node
Node * Iterative_Reverse(Node *head)
{
   Node *prevNode = NULL;      //pointer to the previous node
   Node *nextNode = NULL;      //pointer to the next node
   Node *currentNode = head;   //pointer to the current node
   while(currentNode)
   {
       nextNode = currentNode->next; //save the pointer to the next node
                                     //otherwise we will lose it as we
                                     // overwrite it in the next step
       currentNode->next = prevNode; //reverse the link
      
       prevNode = currentNode; //set the current node as the previous node
                               //for the next iteration
       currentNode = nextNode; //advance the current pointer
   }
   return prevNode;
}

Linked List: Delete Node

Question: You are given a pointer to a node in a singly linked list. The head pointer is not available. Your task is to delete the specified node.

Solution: Typically, deleting a node from a singly linked list requires us to have the pointer to the node before the node to be deleted. We need this previous pointer so we can set it's Next pointer to the node after the specified node to be deleted. In this problem since we do not have the head pointer, we cannot walk the list and get the previous pointer.

We need to start thinking about what information does a linked list node have. Typically it has one or more data variables and a Next pointer that points to the next node in the linked list. If we were to overwrite the data in the specified node to be deleted from the next node in the list and delete this next node instead of the specified node, we would have effectively deleted the node. Technically, we don't delete the specified node but delete the next node after we copy data from it.

Note: This approach does not work in the case where the specified node to be deleted is the last node in the linked list.

Code: typedef struct _node

{
 int i;
 struct _node *next;
} Node;

void DeleteNode(Node *deleteThisNode)
{
  if(deleteThisNode->next != null)                  //only if the specified node is not the last node of the list
                                                    // this approach does not work in that case
  {
      deleteThisNode->i = deleteThisNode->next->i;  //copy data from the next node
      Node * freeThis = deleteThisNode->next;       //save the ptr to the next node, so we can free it
      deleteThisNode->next = deleteThisNode->next->next;  //point the Next pointer to the node after deleteThisNode->next
      free(freeThis);                               //don't forget to free memory
  }
}

Linked List: Find the middle element

Question: Given a singly linked list, find the node in the middle.

Solution 1: Walk the linked list to find the length of the list. Lets say n is the length of the list. Walk the list again upto ⌊ n/2 ⌋.

Solution 2: Use two pointers. Move one pointer at twice the speed of the second. When the 1st pointer reaches the end of the list, the 2nd pointer will be pointing to the middle node. Note: If the list has even number of nodes, the middle node will be floor of ⌊ n/2 ⌋.

Code:

Node * FindMiddle(Node *listHead)
{
  Node *ptr1, *ptr2;  // we need 2 pointers
  ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

  int i=0;

  while(ptr1->next != NULL) // keep looping until we reach the tail
                              // (next will be NULL for the last node)
  {
      if(i == 0)
      {
          ptr1 = ptr1->next; //increment only the 1st pointer
          i=1;
      }
      else if( i == 1)
      {
          ptr1 = ptr1->next; //increment both pointers
          ptr2 = ptr2->next;
          i = 0;
      }
  }
  return ptr2;        //now return the ptr2 which points to the middle node
}

Linked List: Find n-th element from the tail

Question: Given a singly linked list find the n-th node from the back.

Solution 1: Reverse the linked list and select the n-th node from the head of the linked list.

Solution 2: Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Notes: Both solutions take O(n) time but Solution 2 is more elegant.

Code:

//define the list node
typedef struct _node
{
 int i;
 struct _node *next;
} Node;

Node * FindNthFromBack(Node *listHead, int n)
{
    Node *ptr1, *ptr2;  // we need 2 pointers
    ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
    {
        if(n > 0)
        {
            ptr1 = ptr1->next; //increment only the 1st pointer
            n--;
        }
        else
        {
            ptr1 = ptr1->next; //increment both pointers
            ptr2 = ptr2->next;
        }
    }
    return ptr2;    //now return the ptr2 which points to the nth node from the tail
}