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)哈。。。
|
|