在數(shù)據(jù)結(jié)構(gòu)的最高層抽象里，只有兩種結(jié)構(gòu)，數(shù)組和鏈表。這兩種結(jié)構(gòu)，是所有其他數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的基礎(chǔ)。隊列和棧，可以用鏈表和數(shù)組來實現(xiàn)。圖，可以用鄰接表和鄰接矩陣來實現(xiàn)，其中，鄰接表就是鏈表，鄰接矩陣就是數(shù)組。樹，用數(shù)組實現(xiàn)，可以實現(xiàn)堆，用鏈表實現(xiàn)，可以實現(xiàn)二叉樹，AVL樹等等。

所以，鏈表的操作是掌握數(shù)據(jù)結(jié)構(gòu)最基礎(chǔ)的能力。一切數(shù)據(jù)結(jié)構(gòu)的操作，無非就是遍歷+增刪查改。由于每一種數(shù)據(jù)結(jié)構(gòu)有不同的特性，比如，數(shù)組結(jié)構(gòu)，不需要存儲指針，而鏈表結(jié)構(gòu)需要存儲指針。數(shù)據(jù)結(jié)構(gòu)的增刪查改，就是在這些特性的基礎(chǔ)之上來完成的。

關(guān)于鏈表面試算法的第一塊，主要來學(xué)習(xí)鏈表這種數(shù)據(jù)結(jié)構(gòu)，是如何來實現(xiàn)刪除節(jié)點的。

常見的刪除節(jié)點題目有：

刪除鏈表中的節(jié)點_leetcode273

移除鏈表元素_leetcode203

刪除鏈表的倒數(shù)第N個節(jié)點_leetcode19

刪除排序鏈表中的重復(fù)元素_leetcode83

刪除排序鏈表中的重復(fù)元素 II_leetcode82

---

1.刪除鏈表中的節(jié)點

思路分析：

在鏈表中，刪除一個節(jié)點node的常見方法是， 找到該節(jié)點的前驅(qū)節(jié)點，修改節(jié)點的next指針，使其指向node的下一個節(jié)點。

時間復(fù)雜度為O(1)的方法： 把將要刪除的node節(jié)點的值，替換為它的后繼節(jié)點，然后刪除它之后的節(jié)點即可。 但是，這種方法需要保證，被刪除的節(jié)點不是鏈表末尾。 若是末尾，則只能通過找到前序節(jié)點的方法來實現(xiàn)刪除。

被刪除節(jié)點不為尾結(jié)點情況下，代碼演示如下：

class Solution {public void deleteNode(ListNode toBeDeleted) { toBeDeleted.val = toBeDeleted.next.val;toBeDeleted.next = toBeDeleted.next.next;} }

被刪除節(jié)點可能為尾結(jié)點情況下，代碼演示如下：

public static ListNode deleteNode(ListNode head,ListNode toBeDeleted){if(head==null || toBedeleted == null){return head;}// 若被刪除節(jié)點為尾結(jié)點，則遍歷鏈表，找到其前驅(qū)節(jié)點if(toBeDeleted.next == null){ListNode curr = head;while(curr.next!=toBeDeleted){curr = curr.next;}curr.next = null;//直接刪除為節(jié)點}else{toBeDeleted.value = toBeDeleted.next.value;// 待刪除的結(jié)點的下一個指向原先待刪除引號的下下個結(jié)點，即將待刪除的下一個結(jié)點刪除 toBeDeleted.next = toBeDeleted.next.next;}//return head;}

---

2.移除鏈表元素

思路：

方法：啞結(jié)點+雙指針 步驟：設(shè)置前驅(qū)指針pre和工作指針cur來遍歷數(shù)組，若發(fā)現(xiàn)目標值，則刪除，否則，一起向前。

代碼：

class Solution {public ListNode removeElements(ListNode head, int val) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode pre = dummy;ListNode cur = head;while(cur!=null){if(cur.val==val){pre.next = cur.next;cur = cur.next;}else{pre=cur;cur=cur.next;}}return dummy.next; } }

---

3.刪除鏈表的倒數(shù)第N個節(jié)點

思路：

使用兩個指針，首先，p1指向頭結(jié)點，p2指向第n+1個節(jié)點。 然后，p1,p2兩個指針同時向后移動。當p2指向尾節(jié)點時，p1指向的便是倒數(shù)第n+1個節(jié)點。 倒數(shù)第n+1個節(jié)點為倒數(shù)第n個節(jié)點的前驅(qū)。 難點：如何定位到第n個節(jié)點，這個需要特別注意。使用for循環(huán)定位比使用while循環(huán)定位更易理解。巧用啞結(jié)點，避免空指針等多種情況的討論。

當不使用啞結(jié)點來進行運算時，代碼如下：

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode p=head;int len=0;while (p!=null){p=p.next;++len;}if(len<n)return null;if(len==n) return head.next;ListNode p1=head,p2=head;// p1指向第一個數(shù)，需要移動n步，才能指向第n+1個數(shù),此時p1與p2的距離為n。for(int i=1;i<=n;i++){p1=p1.next;}while (p1.next!=null){p1=p1.next;p2=p2.next;}p2.next=p2.next.next;return head; }

使用啞結(jié)點的方式代碼如下：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);dummy.next = head;ListNode p1 = dummy;// p1實際上為被刪除節(jié)點的前驅(qū)節(jié)點，即倒數(shù)第n+1個節(jié)點。ListNode p2 = dummy;// p2移動n步，指向原鏈表中的第n個節(jié)點，此時p1與p2之間的距離為n.for(int i=1;i<=n;i++){p2 = p2.next;}// p1,p2同時向后移，當p2指向尾節(jié)點時，p1指向倒數(shù)第n+1個節(jié)點while(p2.next!=null){p1=p1.next;p2=p2.next;}p1.next = p1.next.next;return dummy.next;} }

---

4. 刪除排序鏈表中的重復(fù)元素

題目：

注意事項：

在鏈表題中，需要注意的是操作鏈表的結(jié)點指針，一定要做非空檢查，避免報空指針異常。

思路：

因為輸入的列表已排序， 因此我們可以通過將結(jié)點的值與它之后的結(jié)點進行比較來確定它是否為重復(fù)結(jié)點。 如果它是重復(fù)的，我們更改當前結(jié)點的 next 指針，以便它跳過下一個結(jié)點并直接指向下一個結(jié)點之后的結(jié)點。

代碼如下：

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur = head;while(cur!=null && cur.next !=null){if(cur.val==cur.next.val){cur.next = cur.next.next;}else{cur = cur.next;}}return head;} }

---

5. 刪除排序鏈表中的重復(fù)元素 II

題目：

給定一個排序鏈表，刪除所有含有重復(fù)數(shù)字的節(jié)點，只保留原始鏈表中 沒有重復(fù)出現(xiàn)的數(shù)字。

思路：

和上一題相比，需要在代碼中實現(xiàn)去重操作。 啞結(jié)點+雙指針法。 啞結(jié)點用于記錄不重復(fù)數(shù)字的頭， p1指向不重復(fù)數(shù)字的最后一位，p2作為工作指針，向前掃描。 去重的判斷條件(p2!=null && p2.next!=null && p2.val !=p2.next.val)

代碼如下：

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dumpy = new ListNode(-1);ListNode p1 = dumpy;ListNode p2 = head;while(p2!=null){if(p2!=null && p2.next!=null && p2.val == p2.next.val){// 若重復(fù)，則實現(xiàn)去重操作int temp = p2.val;while(p2!=null&&p2.val==temp){p2=p2.next;// 去重操作}}else{// 否則將不重復(fù)節(jié)點加入到新鏈表中。ListNode next = p2.next;p2.next = null; // p2和原來節(jié)點斷開p1.next=p2; // 將閹割后的p2節(jié)點加到p1上p1 = p2;p2 = next;}}return dumpy.next;} }

---

總結(jié)

從上述的五道鏈表刪除題可以看出，這種題目常見的技巧是使用啞結(jié)點+雙指針來做，可以避免很多非空的判斷，使得代碼健壯且簡潔。

總結(jié)

以上是生活随笔為你收集整理的链表排序c++代码_[链表面试算法](一) 链表的删除-相关题型总结（6题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。