c++ - 改变链表

Question

你会得到一个单链表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.

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

Answer 1

我会有两个迭代器。让一个（迭代器 A）遍历列表，当你碰到一个数字时停止，让另一个（迭代器 B）停留在列表的开头。当您点击一个数字时，在迭代器 B 的节点之后插入迭代器 A 的节点，然后将迭代器 B 向上移动。这样您就不必单独列出清单。

编辑：在迭代器 A 中插入 B 后删除该项目（感谢 Tudor 的捕获）。

Answer 2

取 2 个指针并增加第 2 个指针，直到你得到一个数字，一旦你得到一个数字，就从这里删除节点并在第一个指针之后插入。

由于它是一个面试问题，面试官可能正在查看您如何处理所有极端情况，例如列表为空，只有两个节点（1-char 和 1-int），字符节点和整数节点的数量在一个块等