你可以接受你BF的EX一起做好朋友吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Love - 情爱幽幽

你可以接受你BF的EX一起做好朋友吗？

你可以接受你BF的EX一起做好朋友吗？# Love - 情爱幽幽

b*v2010-09-07 07:09

1 楼

在这个帖子里有这么一道题：
http://mitbbs.com/article/JobHunting/31549265_3.html
“两链表共享后半部分，找出共享的第一个节点。从最简单的n^2算法写起，然后是
保存到额外数组从尾部Scan，提示发现用长度差搞两个指针距离不同遍历即可。”
有没有人知道“用长度差搞两个指针距离不同遍历”是什么意思？具体怎么做？

a*d2010-09-07 07:09

2 楼

BF有个在以前一起3年的EX，还同居过。现在仍联系紧密，常常一起去吃饭
，购物。你觉
得不太舒服，但是BF说他们现在只是朋友关系，而且还要你一起作朋友。你可以接受吗
？

r*o2010-09-07 07:09

3 楼

两个长度分别是l1,l2,假定l1>l2,
那么就让第一个链表先开始，等它visit完 l1-l2个节点的时候第2个链表也开始visit。

【在 b******v 的大作中提到】

: 在这个帖子里有这么一道题：
: http://mitbbs.com/article/JobHunting/31549265_3.html
: “两链表共享后半部分，找出共享的第一个节点。从最简单的n^2算法写起，然后是
: 保存到额外数组从尾部Scan，提示发现用长度差搞两个指针距离不同遍历即可。”
: 有没有人知道“用长度差搞两个指针距离不同遍历”是什么意思？具体怎么做？

g*92010-09-07 07:09

4 楼

他们当时为什么分开阿？

【在 a*****d 的大作中提到】

: BF有个在以前一起3年的EX，还同居过。现在仍联系紧密，常常一起去吃饭
: ，购物。你觉
: 得不太舒服，但是BF说他们现在只是朋友关系，而且还要你一起作朋友。你可以接受吗
: ？

b*v2010-09-07 07:09

5 楼

原来是这个意思，多谢！

visit。

【在 r****o 的大作中提到】

: 两个长度分别是l1,l2,假定l1>l2,
: 那么就让第一个链表先开始，等它visit完 l1-l2个节点的时候第2个链表也开始visit。

a*d2010-09-07 07:09

6 楼

听说是他们LONG DISTANCE后就SPLIT了，没什么其它问题，但现在又住一个城市了

【在 g******9 的大作中提到】

:
: 他们当时为什么分开阿？

l*c2010-09-07 07:09

7 楼

first, get the length of the two list O(2n)
count = difference;
move the long one with count steps, then both move one by one, if equal, OK
O(n)

R*o2010-09-07 07:09

8 楼

他们肯定还在做爱，你要制止他们。

【在 a*****d 的大作中提到】

I*A2010-09-07 07:09

9 楼

visit。
怎么知道visit到了the first shared node?

【在 r****o 的大作中提到】

: 两个长度分别是l1,l2,假定l1>l2,
: 那么就让第一个链表先开始，等它visit完 l1-l2个节点的时候第2个链表也开始visit。

a*d2010-09-07 07:09

10 楼

我也考虑过这个，但还没真凭实据

【在 R*****o 的大作中提到】

: 他们肯定还在做爱，你要制止他们。

v*w2010-09-07 07:09

11 楼

是不是说如果知道1长m, 2长n（assume m>n）
p1从1得m-n开始，p2从2的头开始，相等时就是相交处
这个方法访问m+n+(m-k)个节点（k共享部分长度），应该是很不错了，不知道有没有更
好的办法

【在 b******v 的大作中提到】

R*o2010-09-07 07:09

12 楼

不容易找到真凭实据，尤其是边缘性行为，比如口交

【在 a*****d 的大作中提到】

: 我也考虑过这个，但还没真凭实据

I*A2010-09-07 07:09

13 楼

oh, two pointers equal.

OK

【在 l******c 的大作中提到】

: first, get the length of the two list O(2n)
: count = difference;
: move the long one with count steps, then both move one by one, if equal, OK
: O(n)

a*d2010-09-07 07:09

14 楼

你有实际经验吗

【在 R*****o 的大作中提到】

: 不容易找到真凭实据，尤其是边缘性行为，比如口交

s*t2010-09-07 07:09

15 楼

Mmmm....let me write one:
list1:
1-> 2-> 3->4
list2:
5->6->3->4
int countlen(Node node){
int counter = 0;
while(node!=null) {node=node->next; counter++;}
return counter;
}
Node goNstep(Node root, int n){
while(n-->0) root=root->next;
return root;
}
Node getCommon(Node root1, Node root2){
int len1 = countlen(root1);
int len2 = countlen(root2);
if(len1 > len2) root1 = goNstep(root1, len1-len2);
else root2 = goNstep(root2, len2-len1);
while(root1!=NULL){
if(root1 == root2) brea

m*n2010-09-07 07:09

16 楼

这还用问吗？傻妞

【在 a*****d 的大作中提到】

r*o2010-09-07 07:09

17 楼

goNstep里面应该有个n--;

【在 s******t 的大作中提到】

: Mmmm....let me write one:
: list1:
: 1-> 2-> 3->4
: list2:
: 5->6->3->4
: int countlen(Node node){
: int counter = 0;
: while(node!=null) {node=node->next; counter++;}
: return counter;
: }

I*e2010-09-07 07:09

18 楼

坚决不可以.

【在 a*****d 的大作中提到】

s*t2010-09-07 07:09

19 楼

恩恩。我总是很茅草。

【在 r****o 的大作中提到】

: goNstep里面应该有个n--;

S*w2010-09-07 07:09

20 楼

肉条兄经验丰富

【在 R*****o 的大作中提到】

: 他们肯定还在做爱，你要制止他们。

I*A2010-09-07 07:09

21 楼

didn't read your code carefully ah...
does it work with the following case
list 1: 0->1->2->3->4
list 2: 6->7->2->1->0->3->4

【在 s******t 的大作中提到】

: Mmmm....let me write one:
: list1:
: 1-> 2-> 3->4
: list2:
: 5->6->3->4
: int countlen(Node node){
: int counter = 0;
: while(node!=null) {node=node->next; counter++;}
: return counter;
: }