基于Python和C++實現刪除鏈表的節點

給定單向鏈表的頭指針和一個要刪除的節點的值，定義一個函數刪除該節點。

返回刪除后的鏈表的頭節點。

示例 1:

輸入: head = [4,5,1,9], val = 5

輸出: [4,1,9]

解釋: 給定你鏈表中值為 5 的第二個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 1 -> 9.

示例 2:

輸入: head = [4,5,1,9], val = 1

輸出: [4,5,9]

解釋: 給定你鏈表中值為 1 的第三個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 5 -> 9.

思路：

建立一個空節點作為哨兵節點，可以把首尾等特殊情況一般化，且方便返回結果，使用雙指針將更加方便操作鏈表。

Python解法：

class ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: def deleteNode(self, head: ListNode, val: int) -> ListNode: tempHead = ListNode(None) # 構建哨兵節點 tempHead.next = head prePtr = tempHead # 使用雙指針 postPtr = head while postPtr: if postPtr.val == val:prePtr.next = postPtr.nextbreak prePtr = prePtr.next postPtr = postPtr.next return tempHead.next

C++解法：

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };class Solution {public: ListNode* deleteNode(ListNode* head, int val) { ListNode *tempHead = new ListNode(-1); // 哨兵節點,創建節點一定要用new!!!!!!!!!!!!!! tempHead->next = head; ListNode *prePtr = tempHead; ListNode *postPtr = head; while (postPtr) { if (postPtr->val == val) {prePtr->next = postPtr->next; // 畫圖確定指針指向關系，按照箭頭確定指向break; } postPtr = postPtr->next; prePtr = prePtr->next; } return tempHead->next; }};

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持好吧啦網。