b******v 发帖数: 1493 | 1 在这个帖子里有这么一道题:
http://mitbbs.com/article/JobHunting/31549265_3.html
“两链表共享后半部分,找出共享的第一个节点。 从最简单的n^2算法写起,然后是
保存到额外数组从尾部Scan,提示发现用长度差搞两个指针距离不同遍历即可。”
有没有人知道“用长度差搞两个指针距离不同遍历”是什么意思?具体怎么做? |
r****o 发帖数: 1950 | 2 两个长度分别是l1,l2,假定l1>l2,
那么就让第一个链表先开始,等它visit完 l1-l2个节点的时候第2个链表也开始visit。
【在 b******v 的大作中提到】 : 在这个帖子里有这么一道题: : http://mitbbs.com/article/JobHunting/31549265_3.html : “两链表共享后半部分,找出共享的第一个节点。 从最简单的n^2算法写起,然后是 : 保存到额外数组从尾部Scan,提示发现用长度差搞两个指针距离不同遍历即可。” : 有没有人知道“用长度差搞两个指针距离不同遍历”是什么意思?具体怎么做?
|
b******v 发帖数: 1493 | 3 原来是这个意思,多谢!
visit。
【在 r****o 的大作中提到】 : 两个长度分别是l1,l2,假定l1>l2, : 那么就让第一个链表先开始,等它visit完 l1-l2个节点的时候第2个链表也开始visit。
|
l******c 发帖数: 2555 | 4 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) |
I**A 发帖数: 2345 | 5
visit。
怎么知道visit到了the first shared node?
【在 r****o 的大作中提到】 : 两个长度分别是l1,l2,假定l1>l2, : 那么就让第一个链表先开始,等它visit完 l1-l2个节点的时候第2个链表也开始visit。
|
v********w 发帖数: 136 | 6 是不是说如果知道1长m, 2长n(assume m>n)
p1从1得m-n开始,p2从2的头开始,相等时就是相交处
这个方法访问m+n+(m-k)个节点(k共享部分长度),应该是很不错了,不知道有没有更
好的办法
【在 b******v 的大作中提到】 : 在这个帖子里有这么一道题: : http://mitbbs.com/article/JobHunting/31549265_3.html : “两链表共享后半部分,找出共享的第一个节点。 从最简单的n^2算法写起,然后是 : 保存到额外数组从尾部Scan,提示发现用长度差搞两个指针距离不同遍历即可。” : 有没有人知道“用长度差搞两个指针距离不同遍历”是什么意思?具体怎么做?
|
I**A 发帖数: 2345 | 7 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)
|
s******t 发帖数: 2374 | 8 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 |
r****o 发帖数: 1950 | 9 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; : }
|
s******t 发帖数: 2374 | 10 恩恩。我总是很茅草。
【在 r****o 的大作中提到】 : goNstep里面应该有个n--;
|
I**A 发帖数: 2345 | 11 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; : }
|
s******t 发帖数: 2374 | 12 这个主要是要比较reference儿不是比较content吧。
while(root1 == root2)
【在 I**A 的大作中提到】 : 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
|
I**A 发帖数: 2345 | 13 nod, right
【在 s******t 的大作中提到】 : 这个主要是要比较reference儿不是比较content吧。 : while(root1 == root2)
|