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. |
C***y
发帖数: 2546 | 2 扫两遍
第一遍： 记录长度，X and Y
第二遍： 长的先走 |X-Y|步，然后同时走，每走一步，判断指针是否相同
。"
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.
|
c**********e
发帖数: 2007 | 3 This is nice. But since we only need to know if the two lists merge, can we
just compare the last nodes of the two lists?
【在 C***y 的大作中提到】
: 扫两遍
: 第一遍： 记录长度，X and Y
: 第二遍： 长的先走 |X-Y|步，然后同时走，每走一步，判断指针是否相同
:
: 。"
: the
|
c****p
发帖数: 6474 | 4 可以
we
【在 c**********e 的大作中提到】
: This is nice. But since we only need to know if the two lists merge, can we
: just compare the last nodes of the two lists?
|
c**********e
发帖数: 2007 | 5 Thanks. Chevy (Chevy)'s method also finds the first common node.
【在 c****p 的大作中提到】
: 可以
:
: we
|
h**********c
发帖数: 4120 | 6 disussucsed with colleague b4
You can use a program like md5.
md5 first list like a file. then second.
finally, you would compare the two md5 program running results.
Do you mean merge identical? |
h*******s
发帖数: 8454 | 7 他说的是俩singly linked list像下面这样
--------\
|
------------------->
等价于有parent指针的树里面的俩节点的lowest common ancestor问题
【在 h**********c 的大作中提到】
: disussucsed with colleague b4
: You can use a program like md5.
: md5 first list like a file. then second.
: finally, you would compare the two md5 program running results.
: Do you mean merge identical?
|
h**********c
发帖数: 4120 | 8 sorry I misunderstood
【在 h*******s 的大作中提到】
: 他说的是俩singly linked list像下面这样
: --------\
: |
: ------------------->
: 等价于有parent指针的树里面的俩节点的lowest common ancestor问题
|
c**********e
发帖数: 2007 | 9 Thanks. That's my understanding, though I do not know more than what is told
literally.
【在 h*******s 的大作中提到】
: 他说的是俩singly linked list像下面这样
: --------\
: |
: ------------------->
: 等价于有parent指针的树里面的俩节点的lowest common ancestor问题
|
