Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Intersection

LinkedList 就活

problem

Write a program to find the node at which the intersection of two singly linked lists begins. - If the two linked lists have no intersection at all, return null.

  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

how to solve

Firstly, I calculate the length of two linked list and advance the pointer by the difference in lengths. Secondly, traverse on each linked list until the pointers are the same.

code

Remove all ads