更改链接列表

给您一个单一链接列表a->b->c->d->1->2->3->4->e->f->g->h->5->6->7->8。你必须改变这个列表看起来像a->1->b->2->c->3->d->4->e->5->f->6->g->7->h->8。更改链接列表

我的方法使用额外的列表，我们从列表中删除数字并将它们分开存储。然后将列表合并在一起。有人可以建议更好的技术来做到这一点？

2012-06-02 nikhil

有什么限制？ – dirkgently

哪种方式更好？时间？空间？ – Tudor

两者都好，如果不是那么时间。 – nikhil

我会有两个迭代器。让一个（迭代器A）遍历列表，当你点击一个数字时停止，并让另一个（迭代器B）停留在列表的开始处。当您点击一个数字时，将迭代器A处的节点插入迭代器B处的节点之后，然后将迭代器B向上移动。通过这种方式，您无需制作单独的列表。

编辑：删除迭代器A中的项目后，您将它插入B（感谢都铎捕捉）。

2012-06-02 20:12:26

您忘了也删除了迭代器A的编号。无论如何，我的+1。 – Tudor

您可以简单地交换指针而不是插入和删除。 – dirkgently

指针的交换如何工作？这不会将b移到错误的地方。 – nikhil

取2个指针并递增第2个指针，直到得到一个数字，并且只要您得到一个数字，就从这里删除节点并在第一个指针之后插入。

既然面试的问题，面试官可能会看你如何处理所有的角落案例如列表为空，只有两个节点（1字符& 1-int），字符节点和整数节点的数目是不同的在一个块中的数量等。

2012-06-03 06:35:56

回答