由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 讨论一道两个linked list的题目
相关主题
这种解法对吗?merge two BST求一题的完美简洁解答
发几道Google面试题(Phone and Onsite)aababccbc remove abc
问个题,怎么比较两个tree是topological same?重新看一道经典题
专家们,find the longest common substring of two strings问个MSFT的题
问个题?求教 合并两数组 并排除重复
这题谁知道答案?做题做得很郁闷,求指点
经典面试题50行code能解决addbinary 问题么
两个Sorted Array,找K smallest element求两个程序的C++ code
相关话题的讨论汇总
话题: node话题: root1话题: root2话题: gonstep话题: len2
进入JobHunting版参与讨论
1 (共1页)
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)

1 (共1页)
进入JobHunting版参与讨论
相关主题
求两个程序的C++ code问个题?
贡献个regular expression DP解法这题谁知道答案?
问一道题(2)经典面试题
airBnb电面面经两个Sorted Array,找K smallest element
这种解法对吗?merge two BST求一题的完美简洁解答
发几道Google面试题(Phone and Onsite)aababccbc remove abc
问个题,怎么比较两个tree是topological same?重新看一道经典题
专家们,find the longest common substring of two strings问个MSFT的题
相关话题的讨论汇总
话题: node话题: root1话题: root2话题: gonstep话题: len2