Solution: Definitely we can traverse one list and hash all the nodes. Then traverse the other list. But if we want a O(1) space complexity, we can try the following two methods:
- Traverse both lists to get the their length. Then move the pointer from the head of the longer list by len(long_list) - len(short_list) steps. Then move both pointers in parallel and compare.
- Traverse one list, make the last node point to the head to form a circle and remember the length l. Move one pointer l steps, starting from the head of the second list. Then also start to move a second pointer, still from the head of the second list. Two pointers move in parallel. The node they meet each other is the intersection point.
No comments:
Post a Comment