更改鏈接列表

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）停留在列表的開始處。當您點擊一個數字時，將迭代器A處的節點插入迭代器B處的節點之後，然後將迭代器B向上移動。通過這種方式，您無需製作單獨的列表。

編輯：刪除迭代器A中的項目後，您將它插入B（感謝都鐸捕捉）。

Answer 2

取2個指針並遞增第2個指針，直到得到一個數字，並且只要您得到一個數字，就從這裏刪除節點並在第一個指針之後插入。

既然面試的問題，面試官可能會看你如何處理所有的角落案例如列表爲空，只有兩個節點（1字符& 1-int），字符節點和整數節點的數目是不同的在一個塊中的數量等。