Reverse Linked Lists – phew!

I am not really a fan of this question but it seems to be quite a favorite question during technical interview. So, lets discuss reversing a linked-list problem at length.
Basically there are two methods of reversing a linked list – iterative and recursive. Lets discuss the iterative method :
Logic: Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.

     
private static void reverseIterative()
        {
                Node prev=null;
                Node current= head;
                Node next=null;
                while(current != null)
                {
                        next = current.next;
                        current.next = prev;
                        prev = current;
                        current = next;
                }
                head = prev;
        }

This is simple and has the following complexity :
Time Complexity: O(n)
Space Complexity: O(1)

The recursive method needs a bit of thinking – lets visualize our problem first.

The logic looks like this :
1) Divide the list in two parts – first node and rest of the linked list.
2) Call reverse for the rest of the linked list.
3) Link rest to first.
4) Fix head pointer

Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3
Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5
Output: 5->4->3->2->1->8->7->6->NULL.

Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */

class ReverseKLL
{
        static class Node
        {
                int data;
                Node next;
                Node(int data)
                {
                        this.data = data;
                        next =null;
                }
        }
        public static Node head = null; //Create head node
        //Recursive Reversal of a group of k elements
        //1. Reverse the first sub-list of k element and keep track of next and previous nodes
        //2. head.next = reverse(next,k ) - recursively call this function on sub-groups
        //3. return prev  - prev becomes new next
        private static Node reverse(Node node, int k)
        {
                Node current = node;
                Node next= node, prev=null;
                int count = 0;
                //reverse first k elements
                while(current != null && count < k)
                {
                        next = current.next;
                        current.next = prev;
                        prev = current;
                        current=next;
                        count ++;
                }
                //next is now pointer to k+1th node. Recursively call reverse
                //for the list starting from that point 
                if (next!=null)
                {
                        node.next = reverse(next,k);
                }
                //prev is the new head
                return prev;
        }
        //utility methods
        //push a node in the ll
        private static void push(int data)
        {
                Node newnode= new Node(data);
                newnode.next = head;
                head = newnode;

        }
        public static void printList(Node node)
        {
                while (node != null)
                {
                        System.out.println(node.data);
                        node = node.next;
                }
        }
        public static void main(String args[])
        {
               ReverseKLL kll = new ReverseKLL();
               kll.push(8);
               kll.push(7);
               kll.push(6);
               kll.push(5);
               kll.push(4);
               kll.push(3);
               kll.push(2);
               kll.push(1);

               kll.printList(head);
               head=kll.reverse(head, 3);
               System.out.println("===========================");
               kll.printList(head);

        }
}

You have the node in a singly linked list. Now Delete it

Given a pointer to a node in a singly linked list, how do you delete the node ?

A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.

Fast solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.

    struct node *temp  = node_ptr->next;
    node_ptr->data  = temp->data;
    node_ptr->next  = temp->next;
    free(temp);

In java, the code would look something like this :

public void deleteNode(Node node){
 Node temp = node.next;
 node.data = temp.data;
 node.next = temp.next;
 //do nothing with temp and let the garbage collector remove it
 }

Reference –

Identical Linked Lists

Two Linked Lists are identical when they have same data and arrangement of data is also same. For example Linked lists a (1->2->3) and b(1->2->3) are identical.

Write a function to check if the given two linked lists are identical.

There are two ways – recursive and iterative. But as always “to iterate is human, to recurse is divine”

Check If the Singly Linked List has a Loop

The list shown above contains a loop – from 5 its connected to 2. There are several incorrect and inefficient methods of finding a loop. The most efficient method is discussed here.

Check If the Singly Linked List is a Palindrome.

The list shows above is a palindrome and we need to check if it is indeed a palindrome. Among several approaches, the following is a simple and easy to understand method.

Algorithm:
   1.  Get the middle of the linked list.
   2.  Reverse the second half of the linked list.
   3.  Compare the first half and second half.
   4.  Construct the original linked list by reversing the
       second half again and attaching it back to the first half

Time Complexity O(n)
Space Complexity O(1)

Intersection of Two Linked Lists.

We have two linked lists which are merged at some point. We need to find the intersection.

This shape is popularly known as Y-Shape intersection also.

Finding of intersection can be done by several methods. Some of them are listed in this excellent article.

We will discuss a simpler approach which works by getting the difference of the counts of elements in two lists and performs at O(m+n) with O(1) complexity.

Merge Sorted Linked Lists.

Given two sorted Linked Lists, we need to merge them into the third list in sorted order. Complexity – O(n)

Solution :

   public Node mergeList(Node a, Node b){
        Node result = null;
        if(a==null)
            return b;
        if(b==null)
            return a;

        if(a.data <= b.data){
            result =a;
            result.next = mergeList(a.next,b);
        }
        else
        {
            result =b;
            result.next = mergeList(b.next,a);
        }
        return result;
    }

Loop in Singly Linked List.

I am sure you must know answer to this by now. Nevertheless, its very easy to miss the most valid answers to this which is the lesser known “Tortoise and Hare Algorithm”

Solution with  – O(n) time complexity

Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.

This solution is "Floyd’s Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".

function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Reverse the linked list in pairs.

The question is like this – if you have a linked list that holds 1 -> 2 -> 3 -> 4 -> X, then after the function has been called the linked list would hold 2 -> 1 -> 4 -> 3 -> X.

Solution :

public void reversePairRecursive(Node n)
{
         int temp;
         if(n==null || n.next ==null)
                return; //base case for empty or 1 element list
         else 
         {
		//Reverse first pair
		temp = n.data;
		n.data = n.next.data;
		n.next.data = temp;

		//Call the method recursively for the rest of the list
		reversePairRecursive(n.next.next);
	}

}


/**
* Reverse the linkedlist in pairs -Iterative version
* @param n
*/
public void reversePairIterative()
{
	Node current = head;
	int temp;

	while(current != null && current.next != null)
	{
		//Swap the pair
		temp = current.data;
		current.data = current.next.data;
		current.next.data= temp;

		//Advance the current pointer twice
		current = current.next.next;
	}
}