j*******a
发帖数: 101 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: jokeslala (文化盲流), 信区: JobHunting
标 题: 讨论 找单链表倒数m的节点
关键字: 单链表 倒数m 节点
发信站: BBS 未名空间站 (Sun Oct 16 10:32:49 2011, 美东)
对于这个问题：找单链表的倒数第m的节点。
资料上说，用两个指针，第一个指针先走m步，然后两个指针一块走，等第一个指针到
了这个链表的end，第二指针指的就是我们要的节点（优化方法）。
这个是个解决方案，但是我觉得的这个方法没有这么大的优点使得每一个资料都给这个
方法。
简单的方法是，先走这个单链表一遍，算出节点的个数是n，然后再找链表中顺数第n-m
的节点。
优化方法，看起来是遍历链表一次，但是每次都是要让两个指针走一步，而且这两个指
针操作完全有可能都导致内存的page faulting。简单方法看起来是遍历了链表两次，
但是每次操作只让一个指针走一步。我甚至觉得这个优化的方法实际比简单方法要性能
差（如果过它的两个指针的next都导致内存cache换页）。
大家说那？ |
d****n
发帖数: 1637 | 2 "简单的方法是，先走这个单链表一遍，算出节点的个数是n，然后再找链表中顺数第n-
m
的节点"
既然是单向ｌｉｎｋｅｄ ｌｉｓｔ，你怎么算出结点ｎ－ｍ ?
你的假设好像建立在ｄｏｕｂｌｅ ｌｉｎｋｅｄ ｌｉｓｔ 上的。 |
D*******a
发帖数: 3688 | 3 walk the list and count
n-
【在 d****n 的大作中提到】
: "简单的方法是，先走这个单链表一遍，算出节点的个数是n，然后再找链表中顺数第n-
: m
: 的节点"
: 既然是单向ｌｉｎｋｅｄ ｌｉｓｔ，你怎么算出结点ｎ－ｍ ?
: 你的假设好像建立在ｄｏｕｂｌｅ ｌｉｎｋｅｄ ｌｉｓｔ 上的。
|
d****n
发帖数: 1637 | 4 题目是“倒数”m element.
【在 D*******a 的大作中提到】
: walk the list and count
:
: n-
|
D*******a
发帖数: 3688 | 5 walk once, get total node count n
walk again from start for only n-m steps
you arrive at mth element from the end
【在 d****n 的大作中提到】
: 题目是“倒数”m element.
|
d****n
发帖数: 1637 | 6 恩，一般来说就是这么找。
但是你看看楼主开始提出的做法，两个指针的approach， 我觉得更smart 一些。
你的做法：
ptr1=start;
n=0;
while(*(++ptr1)) n++;
ptr2=start;
i=0;
while((i++)<=(n-m)) ptr2++;
楼主的第一个approach:
ptr1=start+m;
ptr2=start;
while(*(ptr1++) && *(ptr2++)) ;
两种算法都是ptr2是结果。（忽略边界判断）
我觉得就指针操作而言，楼主的提法更快，coding style 更好些。
我没看明白楼主优化的做法，貌似和第一个一样。
ps.不喜欢2个loop的approach
【在 D*******a 的大作中提到】
: walk once, get total node count n
: walk again from start for only n-m steps
: you arrive at mth element from the end
|
D*******a
发帖数: 3688 | 7 ++ptr is not the way to walk a linkedlist. start+m does not point to mth
element in the linkedlist.
【在 d****n 的大作中提到】
: 恩，一般来说就是这么找。
: 但是你看看楼主开始提出的做法，两个指针的approach， 我觉得更smart 一些。
: 你的做法：
: ptr1=start;
: n=0;
: while(*(++ptr1)) n++;
: ptr2=start;
: i=0;
: while((i++)<=(n-m)) ptr2++;
: 楼主的第一个approach:
|
d****n
发帖数: 1637 | 8 you are right.
My head was fried with pointer of arrays.
But you got it, right?
the solution is to replace increment "++" operation with some fancy ptr->
next();
correct?
【在 D*******a 的大作中提到】
: ++ptr is not the way to walk a linkedlist. start+m does not point to mth
: element in the linkedlist.
|
d****n
发帖数: 1637 | 9 ptr1=ptr2=start;
i=0;
while((i++)<=m) ptr1=ptr1->next();
while(ptr1->next()!=NULL) {
ptr1=ptr1->next() ;
ptr2=ptr2->next();
}
Still two loops, haha.
but the first loop is constant. |
j******n
发帖数: 271 | 10 What is the concern here? In each iteration, at most 4 pointers are
referenced: two pointers to the current and the two pointer to next elements
of them. Even if they are all in different pages, in each iteration we
reference at most 4 pages, which is 4*4KB and can fit in today's L1 cache.
Below is my solution without advancing each pointer twice. Please comment.
1: #include
2: #include
3: #include
4: using namespace std;
5:
6: template
7: typename list::iterator rev_n_th(list& l, size_t n)
8: {
9: if (n < 1)
10: return l.end();
11:
12: vector::iterator> v(n, l.end());
13:
14: size_t j=0;
15: for (typename list::iterator i=l.begin(); i!=l.end(); ++i)
16: {
17: v[j] = i;
18:
19: if (++j == n)
20: j = 0;
21: }
22:
23: return v[j];
24: }
25:
26: int main()
27: {
28: list l;
29: for (int i=1; i<100; ++i)
30: l.push_front(i);
31:
32: for (size_t i=1; i<150; i+=10)
33: {
34: list::iterator p = rev_n_th(l, i);
35: cout << i << ": " << (p==l.end() ? 0 : *p) << endl;
36: }
37:
38: return 0;
39: }
优化方法，看起来是遍历链表一次，但是每次都是要让两个指针走一步，而且这两个指
针操作完全有可能都导致内存的page faulting。简单方法看起来是遍历了链表两次，
但是每次操作只让一个指针走一步。我甚至觉得这个优化的方法实际比简单方法要性能
差（如果过它的两个指针的next都导致内存cache换页）。
【在 j*******a 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: jokeslala (文化盲流), 信区: JobHunting
: 标 题: 讨论 找单链表倒数m的节点
: 关键字: 单链表 倒数m 节点
: 发信站: BBS 未名空间站 (Sun Oct 16 10:32:49 2011, 美东)
: 对于这个问题：找单链表的倒数第m的节点。
: 资料上说，用两个指针，第一个指针先走m步，然后两个指针一块走，等第一个指针到
: 了这个链表的end，第二指针指的就是我们要的节点（优化方法）。
: 这个是个解决方案，但是我觉得的这个方法没有这么大的优点使得每一个资料都给这个
: 方法。
|
c****p
发帖数: 6474 | 11 Even if they are all in different pages, in each iteration we reference at m
ost 4 pages, which is 4*4KB and can fit in today's L1 cache.
上面这话没错但是cache不是这么搞的吧？
elements
【在 j******n 的大作中提到】
: What is the concern here? In each iteration, at most 4 pointers are
: referenced: two pointers to the current and the two pointer to next elements
: of them. Even if they are all in different pages, in each iteration we
: reference at most 4 pages, which is 4*4KB and can fit in today's L1 cache.
: Below is my solution without advancing each pointer twice. Please comment.
: 1: #include
: 2: #include
: 3: #include
: 4: using namespace std;
: 5:
|
d****n
发帖数: 1637 | 12 赞专业，华丽。
elements
【在 j******n 的大作中提到】
: What is the concern here? In each iteration, at most 4 pointers are
: referenced: two pointers to the current and the two pointer to next elements
: of them. Even if they are all in different pages, in each iteration we
: reference at most 4 pages, which is 4*4KB and can fit in today's L1 cache.
: Below is my solution without advancing each pointer twice. Please comment.
: 1: #include
: 2: #include
: 3: #include
: 4: using namespace std;
: 5:
|
