c**********e
发帖数: 2007 | 1 This is from other people's 面经:
"判断两个single linkedlist 是否merge。从naive讲起，说到了linear的两种解法。"
I can think of two approaches:
1. Use hashtable.
2. Use the address of last node of each SLL to compare with each node of the
other SLL
Are these the "linear的两种解法"? Thanks. |
z****4
发帖数: 194 | 2 hashtable怎么用？
。"
the
【在 c**********e 的大作中提到】
: This is from other people's 面经:
: "判断两个single linkedlist 是否merge。从naive讲起，说到了linear的两种解法。"
: I can think of two approaches:
: 1. Use hashtable.
: 2. Use the address of last node of each SLL to compare with each node of the
: other SLL
: Are these the "linear的两种解法"? Thanks.
|
h*****f
发帖数: 248 | 3 you mean detecting duplicate elements in 2 linked lists? |
P*******U
发帖数: 203 | 4 I think these are the two linear methods, roughly, both are O(n+m) |
g*********e
发帖数: 14401 | 5 count the number of nodes in each list,
then move the longer list |Na-Nb| steps， then move both list
if they merge, the two pointer would be equivalent at some point.
O(n+m) |
P*******U
发帖数: 203 | 6 In lz's description, only required to decide whether merge, but not asked to
find the merge place. Then comparing the last element is enough and much
simpler than your algo.
【在 g*********e 的大作中提到】
: count the number of nodes in each list,
: then move the longer list |Na-Nb| steps， then move both list
: if they merge, the two pointer would be equivalent at some point.
: O(n+m)
|
