Tuesday, November 1, 2011

Common node in linked lists

Given the heads of two linked lists, find whether they have any common node. If yes, find the common node.
Try to solve it as elegantly as possible.

Solution:
  1. Subtract the length of smaller list from the larger one.
  2. Move a pointer ahead on larger list by the difference of lengths.
  3. Now put a pointer on head of smaller list.
  4. More two pointers together.
  5. The point at which they meet is the point where they short.

Code : 

Node *getShortedNode(Node *list1, Node *list2){
int d = length(list1) - length(list2);

if(d < 0){

d = d * (-1);
Node *tmp = list1;
list1 = list2;
list2 = tmp;
}

Node *ptr1 = list1;
for(int i=0; i<d; i++){

ptr1 = ptr->next;
}

Node *ptr2 = list2;
while(ptr1 != NULL){

if(ptr1 == ptr2)
break;
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

return ptr1;
}

int length(Node *list){

int count = 0;
while(list != NULL){

list = list->next;
count++;
}
return count;
}

Complexity :
  • Time : O(N)
  • Space : O(1)

No comments:

Post a Comment