j*****n
发帖数: 1545 | 1 小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
有一个循环链表 a->d->b->c->e->....->a
每一个节点都是一个整数，且不重复(除了首尾节点外)。
现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
我想重新把链表建立起来，应该用什么样的算法?
谢谢. | j****a
发帖数: 1277 | 2 可以先排序在恢复链表 O(nlogn)
要不哈希一下也行
【在 j*****n 的大作中提到】
: 小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
: 有一个循环链表 a->d->b->c->e->....->a
: 每一个节点都是一个整数，且不重复(除了首尾节点外)。
: 现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
: 的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
: 我想重新把链表建立起来，应该用什么样的算法?
: 谢谢.
| j*****n
发帖数: 1545 | 3
没怎么明白，怎么排序阿，那些节点的整数值是没大小规律的。
能稍微详细点吗?
【在 j****a 的大作中提到】
: 可以先排序在恢复链表 O(nlogn)
: 要不哈希一下也行
| DK
发帖数: 194 | 4 hash 比较好吧。。。先把全部放进hashtable,用每个segment的第二个节点做key,把
segment做value,然后traverse整个table,每个entry都可以找到他的上家，然后 就连
上了,应该是O(n)哈。。。 | j****a
发帖数: 1277 | 5 按第一个字母排序 nlogn
a->d时 要找d开头的节点 logn
traverse一边 整体还是nlogn
【在 j*****n 的大作中提到】
:
: 没怎么明白，怎么排序阿，那些节点的整数值是没大小规律的。
: 能稍微详细点吗?
| j*****n
发帖数: 1545 | 6
看来大家都觉得Hash比较好, 我得回去补补，都忘了Hash查找怎么回事了
【在 DK 的大作中提到】
: hash 比较好吧。。。先把全部放进hashtable,用每个segment的第二个节点做key,把
: segment做value,然后traverse整个table,每个entry都可以找到他的上家，然后 就连
: 上了,应该是O(n)哈。。。
|
|
