Finding the intersecting node from two intersecting linked lists

by

This takes O(M+N) time and O(1) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)

  1. Traverse the two linked list to find M and N.
  2. Get back to the heads, then traverse |M − N| nodes on the longer list.
  3. Now walk in lock step and compare the nodes until you found the common ones.

Edit: See more here.

More Related Contents:

  1. How to reverse a singly linked list using only two pointers?
  2. Linked list recursive reverse
  3. Merging two sorted linked lists
  4. Recursive and non-recursive traversal of three degree tree
  5. how to show time performance for merge sort? [closed]
  6. Why this C code makes infinite loop?
  7. Debugging a linked-list
  8. The most efficient way to implement an integer based power function pow(int, int)
  9. Efficient Algorithm for Bit Reversal (from MSB->LSB to LSB->MSB) in C
  10. What integer hash function are good that accepts an integer hash key?
  11. Unique random number generation in an integer array [duplicate]
  12. Calculating factorial of large numbers in C
  13. Combine Gyroscope and Accelerometer Data
  14. Using pointers to remove item from singly-linked list
  15. Power by squaring for negative exponents
  16. C How to “draw” a Binary Tree to the console [closed]
  17. How to do unsigned saturating addition in C?
  18. Traverse Matrix in Diagonal strips
  19. Program to print permutations of given elements [closed]
  20. Rationale behind the container_of macro in linux/list.h
  21. Gaussian elimination without result for acceleration
  22. Fastest way to calculate a 128-bit integer modulo a 64-bit integer
  23. Lookups on known set of integer keys
  24. Sorting an array in C?
  25. Find maximum of three number in C without using conditional statement and ternary operator
  26. forwarding (drawing) line in 3d grid
  27. Algorithm to generate bit mask
  28. How to implement a linked list in C?
  29. Variable Sized Arrays vs calloc in C
  30. A possible algorithm for determining whether two strings are anagrams of one another? [closed]

Leave a Comment