g*******s
发帖数: 490 | 1 就是有2个linkedlist，size都为n, 他们可能merge，就是share at least on common
node，问怎么判断是否merge，找
那个common node.
naive的方法就是2个loop，比较address了。o(n squre)
我想了个方法就是，2个list按address排序，这样是o(nlogn)，然后比较address in
two sorted list, 这样是o(n)。
还有更好的办法么？ |
c****o
发帖数: 41 | 2 假如merge的话，tail 应该是一样的。所以从两个head开始往前走到tail，看看两个
tail是不是相
等就可以了
common
【在 g*******s 的大作中提到】
: 就是有2个linkedlist，size都为n, 他们可能merge，就是share at least on common
: node，问怎么判断是否merge，找
: 那个common node.
: naive的方法就是2个loop，比较address了。o(n squre)
: 我想了个方法就是，2个list按address排序，这样是o(nlogn)，然后比较address in
: two sorted list, 这样是o(n)。
: 还有更好的办法么？
|
g*******s
发帖数: 490 | 3 对。。我傻了＝ ＝，我一直纠结于merge之后还会diverge的想法。。。
【在 c****o 的大作中提到】
: 假如merge的话，tail 应该是一样的。所以从两个head开始往前走到tail，看看两个
: tail是不是相
: 等就可以了
:
: common
|
t****0
发帖数: 235 | 4 me too.
【在 g*******s 的大作中提到】
: 对。。我傻了＝ ＝，我一直纠结于merge之后还会diverge的想法。。。
|
h**********d
发帖数: 4313 | 5 对。。。那样是O(2N)了吧
【在 c****o 的大作中提到】
: 假如merge的话，tail 应该是一样的。所以从两个head开始往前走到tail，看看两个
: tail是不是相
: 等就可以了
:
: common
|
c***2
发帖数: 838 | 6 since both sizes are n, if they converge, it must be a symetrical Y.
so one loop to traverse both simutaneously and check whether two addresses
are equal to get the common one. |
J******t
发帖数: 1945 | 7 typedef struct node
{
int data;
struct node * next;
}Node;
/* O(n) solution */
Node * findCommonNodes(Node * head1, Node * head2)
{
while(head1)
{
if (head1 == head2)
{
return head1;
}
else
{
head1 = head1->next;
head2 = head2->next;
}
}
return NULL;
}
【在 c***2 的大作中提到】
: since both sizes are n, if they converge, it must be a symetrical Y.
: so one loop to traverse both simutaneously and check whether two addresses
: are equal to get the common one.
|
y*****2
发帖数: 294 | 8 为啥tail就一定相等
【在 c****o 的大作中提到】
: 假如merge的话，tail 应该是一样的。所以从两个head开始往前走到tail，看看两个
: tail是不是相
: 等就可以了
:
: common
|
g*****k
发帖数: 623 | 9 share the same common node, then it must have the same next pointer.
【在 y*****2 的大作中提到】
: 为啥tail就一定相等
|
g*****k
发帖数: 623 | 10 This is wrong, suppose the same node appears 2nd in the first list
and 3rd in the second list.
So your code only solves the problem when the same node is at the same rank
in
each list.
typedef struct node
{
int data;
struct node * next;
}Node;
/* O(n) solution */
Node * findCommonNodes(Node * head1, Node * head2)
{
while(head1)
{
if (head1 == head2)
{
return head1;
}
else
{
head1 = head1->next;
head2 = head2->next;
}
}
return NULL;
}
【在 J******t 的大作中提到】
: typedef struct node
: {
: int data;
: struct node * next;
: }Node;
: /* O(n) solution */
: Node * findCommonNodes(Node * head1, Node * head2)
: {
: while(head1)
: {
|
|
|
y*****a
发帖数: 221 | 11 题目说了两个linked list size 相等
rank
【在 g*****k 的大作中提到】
: This is wrong, suppose the same node appears 2nd in the first list
: and 3rd in the second list.
: So your code only solves the problem when the same node is at the same rank
: in
: each list.
:
: typedef struct node
: {
: int data;
: struct node * next;
|
g*****k
发帖数: 623 | 12 I see
【在 y*****a 的大作中提到】
: 题目说了两个linked list size 相等
:
: rank
|
c***2
发帖数: 838 | 13 good one.
Also I like your "head picture". She is also my favorite.
Met a girl who looks like Zhao YaZhi when I was in college.
Fallen love with her, but pitfully both of us are married... sigh........
【在 J******t 的大作中提到】
: typedef struct node
: {
: int data;
: struct node * next;
: }Node;
: /* O(n) solution */
: Node * findCommonNodes(Node * head1, Node * head2)
: {
: while(head1)
: {
|
b******y
发帖数: 660 | 14 Like your story :-)
【在 c***2 的大作中提到】
: good one.
: Also I like your "head picture". She is also my favorite.
: Met a girl who looks like Zhao YaZhi when I was in college.
: Fallen love with her, but pitfully both of us are married... sigh........
|
d********w
发帖数: 363 | 15 大家可以看这个
http://geeksforgeeks.org/?p=2405
详细叙述了在通用情况下的算法
common
【在 g*******s 的大作中提到】
: 就是有2个linkedlist，size都为n, 他们可能merge，就是share at least on common
: node，问怎么判断是否merge，找
: 那个common node.
: naive的方法就是2个loop，比较address了。o(n squre)
: 我想了个方法就是，2个list按address排序，这样是o(nlogn)，然后比较address in
: two sorted list, 这样是o(n)。
: 还有更好的办法么？
|
