Find common node of two linked list - intersecting node of two singly linked list

In order to find common node of two linked lists we need to consider one of the important factor - length of linked list. If length of both linked list is same then it is just a cake walk, iterate both linked list with same frequency(one node at a time) and check whether both linked list reference same node at any point, if intersection node exist we will find it, else reaches at end of list. However, problem is all about two linked list of different length.Refer following diagram, length of first linked list is 4 and 3 for second one. We will start with brute force approach followed by some time efficient ways.

Brute force approach- Iterate any given linked list for every node of another linked list and compare if both nodes are equals or not, if at any moment nodes passes equals() test that nodde is common node, otherwise no common node exist. Time and space complexity :- Suppose length of linked lists are p and q respectively then, time complexity is O(pq) and space complexity is O(1).
Below is sample code for finding intersecting/common node of two linked list.

/* Find common node, intersection of two Linked list- brute force approach */
private static Node getCommonNodeBruteForce(Node head1, Node head2) {
 Node commonNode = null;
 Node current = head2;
 if (head1 != null && head2 != null)
  /*For each node of linked list 1, traverse linked list 2*/
  while (head1 != null) {
 while (current != null) {
  if (current.equals(head1)) {
   commonNode = current;
   break;
  }
  current = current.next;
 }
 /*If commonNode is not null, it means we have found common node*/
 if (commonNode != null) {
  break;
 }
 /* Move linked list 1 head and reset current 
  * to head2 (for each node of linked list 1, traverse linked list 2)
  * */
   head1 = head1.next;
   current = head2;
  }
 return commonNode;
}

By finding length of linked lists:- Can we make this problem easy by making length of each given linked list same and iterate over it. Follow below steps and associated time complexity.
1. Find length of each linked list and its time complexity would be O(p) + O(q) = O(max(p,q))
2. Find difference in length(say d = p- q) in O(1) time. (If d = 0, skip step 3)
3. Traverse d node in longer linked list and it takes O(d) time.
4. Now, we are in position to traverse both linked list together one node at a time and find intersecting node,if exist.
Time and space complexity:- Considering length of linked lists are p and q respectively then, time complexity is O(max(p,q)) and space complexity is O(1).
Below is sample code for finding intersecting/common node of two linked list, improving time complexity.

/* Find common node, intersection of two Linked list- efficient approach */
private static Node getCommonNodeByFindingLength(Node head1, Node head2) {
 Node commNode = null;
 // find length of each linked lists
 int length1 = lengthOfList(head1);
 int length2 = lengthOfList(head2);
 int lengthDiff = length1 > length2 ? (length1 - length2)
   : (length2 - length1);
 /*skip lengthDiff nodes so that both nodes become of equal length */
 if (lengthDiff != 0) {
  if (length1 > length2) {
   while (lengthDiff != 0) {
    head1 = head1.next;
    lengthDiff -= 1;
   }
  } else {
   while (lengthDiff != 0) {
    head2 = head2.next;
    lengthDiff -= 1;
   }
  }

 }
 /* Now both list is of equal length - iterate one node at a time */
 while (head1 != null) {
  if (head1.equals(head2)) {
   commNode = head1;
   break;
  }
  head1 = head1.next;
  head2 = head2.next;
 }
 return commNode;
}

Using two stack :- Suppose we move in backward direction from end of the both linked lists and the moment we notice that we retrieved different node from stack, previous node was the common node of given linked lists.So, which data structure will help in such situation - Stack since it has LIFO (last in first out) properties. Below algorithm explains in detail :-
1. Create two stack and push all nodes in these stacks(linked list -1 in stack-1 and linked list-2 in stack-2)
2. Now, do pop() operation on both stack and compare both nodes,
if passes equals() test - reference this node with a temporary Node variable. otherwise, break loop because - either previous node was common or common node does not exist.
3. Repeat step 2 until equals() test is passed and keep storing previous Node reference.
Time and space complexity:- Since we have used spaces for storing p and q nodes so space complexity is order of O(p+q). For each stack of length p and q, we have to traverse p and q nodes so time complexity is O(p+q).
Below is the sample code for the finding common node using two stacks
```
/* Using stack- finding common node of two linked list */
private static Node findCommonNodeUsingStacks(Node head1, Node head2) {
 Node commonNode = null;
 Node previousTempCommonNode = null;
 Stack<Node> stack1 = new Stack<>();
 Stack<Node> stack2 = new Stack<>();
 /* Push all elements of linked list-1 into stack-1 */
 while (head1 != null) {
  stack1.push(head1);
  head1 = head1.next;
 }
 /* Push all elements of linked list-2 into stack-2 */
 while (head2 != null) {
  stack2.push(head2);
  head2 = head2.next;
 }
 while (!stack1.isEmpty() && !stack2.isEmpty()) {
  if (stack1.peek().equals(stack2.peek())) {
   previousTempCommonNode = stack1.peek();
   stack1.pop();
   stack2.pop();
  } else {
   break;
  }
 }
 /*
  * Check whether temporary node is null or not, if not that node is
  * common node
  */
 if (previousTempCommonNode != null) {
  commonNode = previousTempCommonNode;
 }
 return commonNode;
}
```

Complete program for finding common node using all three methods discussed above.

package com.devinline.linkedlist;

import java.util.Stack;

public class FindCommonNodeOfTwoLL {

 /* Find common node, intersection of two Linked list- brute force approach */
 private static Node getCommonNodeBruteForce(Node head1, Node head2) {
  Node commonNode = null;
  Node current = head2;
  if (head1 != null && head2 != null){
   /* For each node of linked list 1, traverse linked list 2 */
   while (head1 != null) {
   while (current != null) {
    if (current.equals(head1)) {
     commonNode = current;
     break;
    }
    current = current.next;
   }
   /* If commonNode is not null, it means we have found common node */
   if (commonNode != null) {
    break;
   }
   /*
    * Move linked list 1 head and reset current to head2 (for each
    * node of linked list 1, traverse linked list 2)
    */
   head1 = head1.next;
   current = head2;
   }
  }
  return commonNode;
 }

 /* Find common node, intersection of two Linked list- efficient approach */
 private static Node getCommonNodeByFindingLength(Node head1, Node head2) {
  Node commNode = null;
  // find length of each linked lists
  int length1 = lengthOfList(head1);
  int length2 = lengthOfList(head2);
  int lengthDiff = length1 > length2 ? (length1 - length2)
    : (length2 - length1);
  /* skip lengthDiff nodes so that both nodes become of equal length */
  if (lengthDiff != 0) {
   if (length1 > length2) {
    while (lengthDiff != 0) {
     head1 = head1.next;
     lengthDiff -= 1;
    }
   } else {
    while (lengthDiff != 0) {
     head2 = head2.next;
     lengthDiff -= 1;
    }
   }

  }
  /* Now both list is of equal length - iterate one node at a time */
  while (head1 != null) {
   if (head1.equals(head2)) {
    commNode = head1;
    break;
   }
   head1 = head1.next;
   head2 = head2.next;
  }
  return commNode;
 }

/* Using stack- finding common node of two linked list */
private static Node findCommonNodeUsingStacks(Node head1, Node head2) {
 Node commonNode = null;
 Node previousTempCommonNode = null;
 Stack<Node> stack1 = new Stack<>();
 Stack<Node> stack2 = new Stack<>();
 /* Push all elements of linked list-1 into stack-1 */
 while (head1 != null) {
  stack1.push(head1);
  head1 = head1.next;
 }
 /* Push all elements of linked list-2 into stack-2 */
 while (head2 != null) {
  stack2.push(head2);
  head2 = head2.next;
 }
 while (!stack1.isEmpty() && !stack2.isEmpty()) {
  if (stack1.peek().equals(stack2.peek())) {
   previousTempCommonNode = stack1.peek();
   stack1.pop();
   stack2.pop();
  } else {
   break;
  }
 }
 /*
  * Check whether temporary node is null or not, if not that node is
  * common node
  */
 if (previousTempCommonNode != null) {
  commonNode = previousTempCommonNode;
 }
 return commonNode;
}

 class Node {

  private int data;
  private Node next; // reference(handler) for next Node.

  public Node(int data) {
   this.data = data;
   this.next = null;
  }

  public Node getNext() {
   return next;
  }

  public void setNext(Node next) {
   this.next = next;
  }

  public int getData() {
   return data;
  }
 }

 /* Display data of nodes/iterate linked list */
 private static void iterateLinedList(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("[");
   while (current != null) {
    System.out.print(current.getData() + " ");
    current = current.getNext();
   }
   System.out.print(" ]\n");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 /* Find length of linked list */
 private static int lengthOfList(Node head) {
  Node current = head;
  int length = 0;
  if (head != null) {
   while (current != null) {
    current = current.getNext();
    length += 1;
   }
  }
  return length;
 }

 public static void main(String[] args) {
  Node head1;
  Node head2;
  /* First linked list fomation */
  FindCommonNodeOfTwoLL cyc = new FindCommonNodeOfTwoLL();
  Node node1 = cyc.new Node(12);
  head1 = node1;
  Node node2 = cyc.new Node(18);
  Node node3 = cyc.new Node(172);
  Node node4 = cyc.new Node(62);
  Node node5 = cyc.new Node(632);
  head1.next = node2;
  head1.next.next = node3;
  head1.next.next.next = node4;
  head1.next.next.next.next = node5;

  /* Second linked list fomation */
  Node node12 = cyc.new Node(121);
  head2 = node12;
  Node node22 = cyc.new Node(89);
  Node node32 = cyc.new Node(72);
  Node node42 = cyc.new Node(162);
  Node node52 = cyc.new Node(34);
  Node node62 = cyc.new Node(2);
  head2.next = node22;
  head2.next.next = node32;
  head2.next.next.next = node42;
  head2.next.next.next.next = node52;
  head2.next.next.next.next.next = node62;
  node62.next = node4;
  System.out.print("Linked list -1  ");
  iterateLinedList(head1);
  System.out.print("Linked list -2  ");
  iterateLinedList(head2);

  /*
   *         12 -->18-- >172 -->62 -->632 
   *        ^ 
   *        | 
   *     121-->89-->72-->162-->34--> 2
   */
  Node commonNode1 = getCommonNodeBruteForce(head1, head2);
  if (null != commonNode1) {
   System.out.println("Common node of two linked list is with "
     + "value(Brute force approach - O(pq)) : "
     + commonNode1.data);
  }
  Node commonNode2 = getCommonNodeByFindingLength(head1, head2);
  if (null != commonNode1) {
   System.out.println("Common node of two linked list is with "
     + "value(By finding length- O(max(p,q))) : "
     + commonNode2.data);
  }
  Node commonNode3 = findCommonNodeUsingStacks(head1, head2);
  if (null != commonNode1) {
   System.out.println("Common node of two linked list is with "
     + "value(using two stack- O(p+q)) : "
     + commonNode3.data);
  }

 }
}

======Sample output============
Linked list -1 [12 18 172 62 632 ]
Linked list -2 [121 89 72 162 34 2 62 632 ]
Common node of two linked list is with value(Brute force approach - O(pq)) : 62
Common node of two linked list is with value(By finding length- O(max(p,q))) : 62
Common node of two linked list is with value(using two stack- O(p+q)) : 62

==============================

Find common node of two linked list - intersecting node of two singly linked list

1 Comments

Contact Form