删除链表的节点（Python and C++解法）
2021-05-01 04:28
标签：哨兵 stp 方便 while class __init__ 特殊情况 c++ 返回 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 1: 输入: head = [4,5,1,9], val = 5 输入: head = [4,5,1,9], val = 1 来源：力扣（LeetCode） 建立一个空节点作为哨兵节点，可以把首尾等特殊情况一般化，且方便返回结果，使用双指针将更加方便操作链表。 删除链表的节点（Python and C++解法） 标签：哨兵 stp 方便 while class __init__ 特殊情况 c++ 返回 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13221084.html题目：
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof思路：
Python解法：
1 class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6
7 class Solution:
8 def deleteNode(self, head: ListNode, val: int) -> ListNode:
9 tempHead = ListNode(None) # 构建哨兵节点
10 tempHead.next = head
11
12 prePtr = tempHead # 使用双指针
13 postPtr = head
14
15 while postPtr:
16 if postPtr.val == val:
17 prePtr.next = postPtr.next
18 break
19 prePtr = prePtr.next
20 postPtr = postPtr.next
21 return tempHead.next
C++解法：
1 struct ListNode {
2 int val;
3 ListNode *next;
4 ListNode(int x) : val(x), next(NULL) {}
5 };
6
7 class Solution {
8 public:
9 ListNode* deleteNode(ListNode* head, int val) {
10 ListNode *tempHead = new ListNode(-1); // 哨兵节点,创建节点一定要用new!!!!!!!!!!!!!!
11 tempHead->next = head;
12
13 ListNode *prePtr = tempHead;
14 ListNode *postPtr = head;
15
16 while (postPtr) {
17 if (postPtr->val == val) {
18 prePtr->next = postPtr->next; // 画图确定指针指向关系，按照箭头确定指向
19 break;
20 }
21 postPtr = postPtr->next;
22 prePtr = prePtr->next;
23 }
24 return tempHead->next;
25 }
26 };