給定單向鏈表的頭指針和一個(gè)要?jiǎng)h除的節(jié)點(diǎn)的值，定義一個(gè)函數(shù)刪除該節(jié)點(diǎn)。

返回刪除后的鏈表的頭節(jié)點(diǎn)。

示例 1:

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

輸出: [4,1,9]

解釋: 給定你鏈表中值為 5 的第二個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.

示例 2:

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

輸出: [4,5,9]

解釋: 給定你鏈表中值為 1 的第三個(gè)節(jié)點(diǎn)，那么在調(diào)用了你的函數(shù)之后，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.

思路：

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

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) # 構(gòu)建哨兵節(jié)點(diǎn) 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); // 哨兵節(jié)點(diǎn),創(chuàng)建節(jié)點(diǎn)一定要用new!!!!!!!!!!!!!! tempHead->next = head; ListNode *prePtr = tempHead; ListNode *postPtr = head; while (postPtr) { if (postPtr->val == val) {prePtr->next = postPtr->next; // 畫圖確定指針指向關(guān)系，按照箭頭確定指向break; } postPtr = postPtr->next; prePtr = prePtr->next; } return tempHead->next; }};

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。