1.10 如何在只給定單鏈表中某個結點的指針的情況下刪除該結點

【出自XM筆試題】

難度系數：★★★★☆

被考察系數：★★★★☆

題目描述：

假設給定鏈表1→2→3→4→5→6→7中指向第5個元素的指針，要求把結點5刪掉，刪除后鏈表變為1→2→3→4→6→7。

分析與解答：

一般而言，要刪除單鏈表中的一個結點p，首先需要找到結點p的前驅結點pre，然后通過pre.next=p.next來實現對結點p的刪除。對于本題而言，由于無法獲取到結點p的前驅結點，因此，不能采用這種傳統的方法。

那么如何解決這個問題呢？可以分如下兩種情況來分析：

1）如果這個結點是鏈表的最后一個結點，那么無法刪除這個結點。

2）如果這個結點不是鏈表的最后一個結點，可以通過把其后繼結點的數據復制到當前結點中，然后用刪除后繼結點的方法來實現。實現方法如下圖所示。

在上圖中，第一步首先把結點p的后繼結點的數據復制到結點p的數據域中；第二步把結點p的后繼結點刪除。實現代碼如下：

程序的運行結果為

算法性能分析：

由于這種方法不需要遍歷鏈表，只需要完成一個數據復制與結點刪除的操作，因此，時間復雜度為O（1）。由于這種方法只用了常數個額外指針變量，因此，空間復雜度也為O（1）。

引申：只給定單鏈表中某個結點p（非空結點），如何在p前面插入一個結點。

分析與解答：

主要思路：首先分配一個新結點q，把結點q插入到結點p后，然后把p的數據域復制到結點q的數據域中，最后把結點p的數據域設置為待插入的值。