The beauty of Linked Lists

Linked list is one of the simplest but most popular datastructures, perhaps because good linked list problems can be solved within 15-20 minutes. Linked list problems are interesting, fun, thought provoking, and easy to describe, which is why they are very common in a programming interview. Microsoft loves asking linked list questions, I mean, you WILL get at least one linked list question if you ever interview with Microsoft!

Wikipedia defines, “a linked list is a data structure consisting of a group of nodes that together represent a sequence”. So, a typical linked list node will have a reference to the next node and a data field. This is called a singly linked list. Therefore, the first node (commonly known as the head) can represent the entire linked list, since one can traverse all the nodes from head by using the next reference. The Java code for the traversal of a linked list is below:

public class LinkedListMain {
    public static void main(String[] args) {
        Node head= new Node(1);// head represent the linked list
        head.next= new Node(2);
        head.next.next= new Node(3);
        Node temp=head;
        while(temp!=null){
            System.out.print(temp.data);
            temp=temp.next;
        }
    }
}
class Node{
    public int data;
    public Node next=null;
    public Node (int data){
        this.data=data;
    }
}

A C implementation will be the following:

struct node{
	struct node *next;
	int v;
};

Let’s quickly start by one of the most common Microsoft questions,

How would you delete a node from a linked list, when you only have access to that node.

First of all, both in C and Java function calls are by value, so ‘current=current.next;’ is not going to work in a function. However, if you have access to the previous node, then ‘previous.next=current.next;’ would delete the current node. But, you only have access to the current node. The only way to solve this problem (as far as I know) is to copy the value of the next node to the current node and delete the next node. Of course, if the current node is the last node this strategy is not going to work (so you have to check for that condition). A C implementation is following:

int remove_node_without_head(struct node *cur_node){
    if(!cur_node || !(cur_node->next))
    	return -1; //failure
	else{
		struct node *next=cur_node->next;
		int ret=cur_node->v;
	    cur_node->v=next->v;
	    cur_node->next=next->next;
	    free(next);
		return ret;
	}
}

Now, we will look into another popular linked list question, which is not as trivial as the previous one:

How will you detect a corrupt singly linked list (a linked list that has a circle in it, i.e., an arbitrary node’s next pointer points to an earlier node)?

The obvious solution is to start with the head and check if it appears in the next pointers of any of the subsequent nodes and repeat the procedure for all the nodes. This gives a Ο(n²) complexity and is not a good solution.

How about we add an extra field to the Node class to identify if the node is already visited or not? While traversing, if we find Node that is already visited then the linked list is corrupt otherwise it is not. This algorithm gives a Ο(n) complexity but requires an additional Ο(n) memory. The solution will look like this (assuming we do not have access to the Node class):

public class LinkedListMain {
    public static void main(String[] args) {
        Node head= new CircleDetectingNode(1);// head represent the linked list
        head.next= new CircleDetectingNode(2);
        head.next.next= new CircleDetectingNode(3);
        head.next.next.next=head.next;
        System.out.print(LinkedListHelper.isCircular((CircleDetectingNode) head)); //should print true
    }

}

class CircleDetectingNode extends Node{
    public boolean isVisited;
    public CircleDetectingNode(int data){
        super(data);
        isVisited=false;
    }
}
class LinkedListHelper{
    public static boolean isCircular(CircleDetectingNode head){
        CircleDetectingNode temp=head;
        while(temp!=null){
            if(temp.isVisited)
                return true;
            temp.isVisited=true;
            temp=(CircleDetectingNode) temp.next;
        }
        return false;
    }
}

This solution can be classified as a ‘good’ solution, if you are facing the problem for the first time. But, it is not an elegant solution at all. Even if we overlook the additional  Ο(n) memory requirement, not only are there many type castings, but the algorithm is also inaccurate. For example, the call to the ‘isCircular(…)’ function twice for a non-circular linked list will always return true, because the ‘isVisited’ field needs to be reset when the algorithm is done. Doing so will require an additional Ο(n) CPU cycle. Although the overall complexity does not change, one can wonder if a better solution exists!

As always, math and logic come to the rescue! Imagine 2 people are moving in a circular track, which has n steps. Say person1 moves 1 step at a time and person2 moves 2 steps at a time. If both start from the same place, one can mathematically prove that they will meet at their starting point (I will not prove it here, but the proof only requires considering two cases: n is even and odd). However, if person2 has a k steps head start, then one can prove that they will meet k steps before the start of the next loop [Proof: For person1 to go n-k steps, person2 would go 2(n-k)+k steps (twice as fast and a k steps head start). Both n-k and 2(n-k)+k mean k steps before the start of the next loop.]

We use the same logic for detecting circle in a linked list. We use two pointers, namely slow and fast, for traversal. In the analogy, fast pointer has a k steps head start means the circle start from node k from start (in that case, at the start of the circle slow would have traversed k nodes and fast would have traversed 2k nodes, therefore fast would be k nodes ahead). The code is as follows:

class LinkedListHelper{
    public static boolean isCircular(Node head){
        Node slow=head;
        Node fast=head;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)
                return true;
        }
        return false;
    }
}

If there is no circle, the algorithm will traverse only n/2 nodes because of the fast pointer. Although the worst case complexity is still Ο(n), this is a very elegant solution.

Let’s now look into two variations of the problem. The problem can be made complex by asking to return the first node of the circle, which is not necessarily the head.

If we revisit the arguments made in the analogy, we can easily find a solution there. The fast pointer is k node ahead means the start of the circle is k nodes from the head and both pointers meet k nodes before the start of the circle. So, when both pointers meet, if we keep moving the slow pointer and start moving another slow pointer from head, both of these slow pointers must meet at the start of the circle. The code will look like following:

class LinkedListHelper{
     public static Node startOfCircle(Node head){
        Node slow=head;
        Node fast=head;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast)
                break;
        }
        if(fast.next==null) // checks if it breaks because of the end of while, if so there is no circle
            return null;
        Node slow2=head;// could have used fast, since we no longer need it
        while(slow!=slow2){
            slow=slow.next;
            slow2=slow2.next;
        }
        return slow;
    }
}

This problem can be combined with another simple problem and a complex problem can be created (something Google, Micosoft, or Amazon do frequently in job interviews). The following problem is an actual interview question asked by Amazon.

Write a function that will return true if a circular singly linked list has duplicate values and false if there are no duplicate values or the linked list is not circular. You can assume that the values are ascii characters ranging from 0 to 127.

How to detect if a sequence has duplicate values or not, can be another blog post. But, here I am going to use the most efficient implementation. Normally, if you do not know the range of the values (if the question would say that values are integers) then you can use a HashMap to count the occurrence of each value. If the question only requires whether a value has previously occurred  or not (like in this question), one can get away with using HashSet. If you do not remember what a HashMap or a HashSet is, do not worry, for this problem you do not need them. Since we know that the values will range from 0 to 127, we will use 4 32-bit integers where each bit will represent each character. When we find a character in the linked list, we will set its corresponding bit to 1. If the bit is already 1, then we know that the character has come before and we will terminate by returning true. If we put these two concepts together the solution becomes,

    
    public boolean isCircularAndDuplicate(){
        int []table= new int[4]; // initialized to 0
        boolean isCircular=false;
        boolean isDuplicate=false;
        LNode<Character> slow=head;
        LNode<Character> fast=head;
        while(fast!=null && fast.next!=null){
            if((table[slow.data/32]&(1<<(slow.data%32)))==0)
                table[slow.data/32]|=(1<<(slow.data%32)); //set the corresponding bit
            else
                isDuplicate=true;
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                isCircular= true;
                break;
            }
        } 
        // upto n-k values are checked for duplicate. If duplicate not found so far and it is circular then continue checking the rest.
        if(isCircular&&!isDuplicate){
            fast=head;
            while(slow!=fast){
                if((table[slow.data/32]&(1<<(slow.data%32)))==0)
                    table[slow.data/32]|=(1<<(slow.data%32));
                else
                    isDuplicate=true;
                slow=slow.next;
                fast=fast.next;
            }
        }
        return isDuplicate&&isCircular;
    }

I will finish the post by giving some of the common interview problems and their solutions. If you do not understand any of those feel free to ask in the comments section. I have also added github links, which contain all the code in this post, test cases, and some problems that I am going to solve in the future.

1. Reverse a singly linked list.

 
public class ReverseList {
	public static LNode<Integer> perform(LNode<Integer> head){
		if(head==null) return null;
		LNode<Integer> ret=head;
		head=head.next;
		ret.next=null;
		while(head!=null){
			LNode<Integer> temp=head;
			head=head.next;
			temp.next=ret;
			ret=temp;
		}
		return ret;
	}
}

2. Write a program that checks if 2 singly linkedlists intersect or not. Can you return the intersecting node? You can assume both of the lists does not have any cycle.

 
public static boolean doesIntersect(LNode<Integer> l1, LNode<Integer> l2){
	if(l1==null || l2==null) return false;
	while(l1.next!=null) l1=l1.next;
	while(l2.next!=null) l2=l2.next;
	return l1==l2;
}
public static LNode<Integer> intersectingNode(LNode<Integer> l1, LNode<Integer> l2){
	int length1=getLength(l1);
	int length2=getLength(l2);
	int diff=length1-length2;
	while(diff>0){
		l1=l1.next;
		diff--;
	}
	while(diff<0){
		l2=l2.next;
		diff++;
	}
	while(l1!=null && l2!=null && l1!=l2){
		l1=l1.next;
		l2=l2.next;
	}
	return l1;
	
}
private static int getLength(LNode<Integer> list){
	int length=0;
	while(list!=null) {
		length++;
		list=list.next;
	}
	return length;
}

3. Implement an algorithm to find the last n elements of a singly linked list.

 
public class Last_N_Elements {
	LNode<Integer> list;
	public Last_N_Elements(LNode<Integer> list) {
		this.list=list;
	}
	public LNode<Integer> calculate(int n){
		LNode<Integer> t1=list;
		LNode<Integer> t2=list;
		while(t1!=null && n>0){
			t1=t1.next;
			n--;
		}
		if(n>0)
			return t2;
		else{
			while(t1!=null){
				t1=t1.next;
				t2=t2.next;
			}
		}
		return t2;
	}

}

4. Add 2 numbers represented by linked lists: each node contains a digit and the digits are reverse order. For example: 123 is represented by 3->2->1 and 905 is represented by 5->0->9 and their addition will be 8->2->0->1 i.e., 1028. You are allowed to traverse each list only once.

 
public class LinkedListAdd {
	private LNode<Integer> num1;
	private LNode<Integer> num2;
	public LinkedListAdd(LNode<Integer> num1, LNode<Integer> num2) {
		this.num1=num1;
		this.num2=num2;
	}
	public LNode<Integer> add() throws Exception{
		return addRecursive(num1, num2, 0);
	}
	private LNode<Integer> addRecursive(LNode<Integer> n1, LNode<Integer> n2,int carry) throws Exception{
		if((n1!=null&&(n1.data<0||n1.data>9))||(n2!=null&&(n2.data<0||n2.data>9)))
			throw new Exception("Bad List.");
		if(n1==null && n2==null && carry==0){
				return null;
		}
		else{		
			int sum = (n1!=null?n1.data:0)+(n2!=null?n2.data:0) +carry;
			LNode<Integer> ret= new LNode<Integer>(sum%10);
			ret.next=addRecursive(n1!=null?n1.next:null,n2!=null?n2.next:null,sum/10);
			return ret;
		}
	}

}

5. Write an algorithm to remove duplicates from an unsorted linked list.

 
public class RemoveDuplicates {
	private LNode<Integer> head;
	public RemoveDuplicates(LNode<Integer> head) {
		this.head=head;
	}
	public void perform(){
		HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>();
		LNode<Integer> t=head;
		LNode<Integer> previous=head;
		while(t!=null){
			if(hash.get(t.data)!=null){
				previous.next=t.next;
			}
			else{
				hash.put(t.data, true);
				previous=t;
			}
			t=t.next;
		}
	}

}

6. Suppose a weird singly linked list has a child pointer that can point to a Node i.e., another linked list (which also has a child pointer). Flatten the list. (if a node has a child then the after flatten, the child’s last node should point to current’s next node and current’s next node should point to its child. Remember the child should also be recursively flattened.).

 
public class FlattenListWithChild {
	private LNodeWithChild<Integer> head;
	public FlattenListWithChild(LNodeWithChild<Integer> head) {
		this.head=head;
	}
	public LNodeWithChild<Integer> flatten(){
		flattenRecursive(head);
		return head;
	}
	private static void flattenRecursive(LNodeWithChild<Integer> head){
		while(head!=null){
			if(head.child!=null){
				flattenRecursive(head.child);
				LNodeWithChild<Integer> t=head.child;
				while(t.next!=null) t=t.next;
				t.next=head.next;
				head.next=head.child;
				head.child=null;
			}
			head=head.next;
		}
	}

}

All problem list: https://github.com/rfaisal/hellouniverse/blob/master/README.md

Java Source: https://github.com/rfaisal/hellouniverse/tree/master/Java/src/linkedlists

C Source: https://github.com/rfaisal/hellouniverse/tree/master/C/linkedlists

Java Unittests: https://github.com/rfaisal/hellouniverse/tree/master/Java/src/unittests

Tagged: , , , , ,

One thought on “The beauty of Linked Lists

  1. zabed akbar March 21, 2013 at 12:17 pm Reply

    Awesome man!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: