快乐的LeetCode --- 面试题18. 删除链表的节点

梦里梦外; 2023-07-24 09:11 43阅读 0赞

**题目描述：**

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

**示例 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.

--------------------

**解题思路1:**

双指针解法 作者：xie-dai-ma-a

--------------------

**代码1：**

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def deleteNode(self, head: ListNode, val: int) -> ListNode:
            if head.val == val:  # 第一个节点就是要删除的节点
                return head.next
    
            pre, cur = head, head.next
            while cur and cur.val != val:  # 遍历链表
                pre, cur = cur, cur.next   # 找到要删除的节点之前，pre是当前cur节点的前序节点
    
            if cur:   # 找到要删除的节点
                pre.next = cur.next  # 跳过该删除的节点
            return head

--------------------

**解题思路2:**

作者： [xie-dai-ma-a][]

--------------------

**代码2：**

class Solution:
        def deleteNode(self, head: ListNode, val: int) -> ListNode:
            if head.val == val:
                return head.next
            res = head
            while head:
                pre = head
                if head.next and head.next.val == val:
                    pre.next = head.next.next
                head = head.next
            return res

代码精简：

class Solution:
        def deleteNode(self, head: ListNode, val: int) -> ListNode:
            if head.val == val:
                return head.next
            res = head
            while res:
                if res.next and res.next.val == val:
                    res.next = res.next.next
                res = res.next
            return head

--------------------

**解题思路3:**

链表的删除都有一个共同操作，加一个空表头，以防止删除的是表头。  
作者：[wan-dou-huang][]

--------------------

**代码3：**

class Solution:
        def deleteNode(self, head: ListNode, val: int) -> ListNode:
            dummy_node = ListNode()
            dummy_node.next = head
            pre = dummy_node
            cur = dummy_node.next
    
            while cur:
                if cur.val == val:
                    pre.next = cur.next
                    return dummy_node.next
                else:
                    pre = pre.next
                    cur = cur.next

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof][https_leetcode-cn.com_problems_shan-chu-lian-biao-de-jie-dian-lcof]

[xie-dai-ma-a]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/shan-chu-lian-biao-de-jie-dian-by-xie-dai-ma-a/
[wan-dou-huang]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/solution/mian-shi-ti-18-ji-de-jia-kong-biao-tou-by-wan-dou-/
[https_leetcode-cn.com_problems_shan-chu-lian-biao-de-jie-dian-lcof]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof