Reverse a singly linked list

If we have a singly linked list like this 1->2->3->4, how can we reverse it so that it becomes 4->3->2->1? The algorithm is pretty simple. We just need to use two extra pointers and traverse the list once. Here is the algorithm in C++:

struct Node
{
  int data; //data
  Node* next; //pointer to next node in the list
};

Node* reverseLinkedList(Node *head)
{
  Node *next = NULL;
  Node *last = NULL;
  while (head != NULL)
  {
    next = head->next;
    head->next = last;
    last = head;
    head = next;
  }
  head = last;

  return head;
}

Our linked list is composed of different Nodes which have a data field and a next field. The next field is a pointer to the next node in the linked list.

Method reverseLinkedList() takes the head node of a list as its argument. It then creates a next pointer to store the next node in the list and a last pointer to store the last node we visit. After that, we traverse the list until our head pointer is null. For each node in the list, we change its next field to the node before it, and we set it as our last visited node. Finally, when we have traversed the whole list, we must set head to last pointer because last is now pointing at the first node in the list while head is pointing to null. After all, we just return head to give access to the beginning of the reversed list.

So, if our list was 1->2->3->4, the reversed list will be 4->3->2->1. As expected, this algorithm takes O(n) time complexity where n is the number of nodes in the list. It also takes O(2) space complexity because we need only 2 additional pointers for any given list.

Merging two sorted linked list

Question: given two sorted linked lists. Merge one to another, so that the result is a sorted linked list.

Let's take a simple case where we have two linked lists of integer such that list1 = 1->3->5->7 and list2 = 1->2->4. Our algorithm must take in these two lists and output either list1 or list2. the catch is that the result must be 1->1->2->3->4->5->7. The result contains all elements of both lists in sorted order.

Assume that we have class called Node such that a Node has a data and next field. data is used to hold an integer and next is the pointer to the next node in the list. Here is one of the solutions to this question written in C++

Node* MergeTwoSortedList(Node* list1, Node* list2)
{
    Node* temp = NULL; //temporary pointer
    Node* slow = NULL; //slow and fast pointer to travel list2
    Node* fast = NULL; 
    Node* head = list2; //keep track the head of the new list2
    
    //merge list1 to list2
    while(list1)
    {
        if(list1->data <= list2->data)
        {
          temp = list1;
          list1 = list1->next;
          temp->next = NULL;
          temp->next = list2;
          list2 = temp;
          head = list2; //update the head pointer
        }
        else
        {
          slow = list2;
          fast = list2->next;
          while(fast != NULL && fast->data <= list1->data)
          {
            slow = slow->next;
            fast = fast->next;
          }
          temp = list1;
          list1 = list1->next;
          temp->next = fast;
          slow->next = temp;
          list2 = temp;
        }
    }
    return head;
}

Explanation:

1. Loop through list1 and examine each node's value. If the current node's value in list1 is smaller or equal to the current node in list2, then we add it to list2 before the current node in list2. After that, we update pointers to the next node in list1 and list2.
2. However, if the current node in list1 is greater than the current node in list2, we'll traverse list2 using slow and fast pointer until our fast pointer is null or is at a node that is greater than the current node in list1. Next, we add the current node in list1 in front of the node pointed to by the slow pointer in list2. Finally, we update the current node in list2 to the node we just took from list1 and the current node in list1 to the next node in list1.
3. In the end, we return head which is the pointer to the head of the new list2 which has all elements from list1 and the old list2 in sorted order.