剑指 Offer 18. 删除链表的节点

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 Offer 18. 删除链表的节点

问题描述

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

返回删除后的链表的头节点。

注意：此题对比原题有改动

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

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

代码实现

   public ListNode deleteNode(ListNode head, int val) {
        if(head == null){
            return null;
        }

        if(head.val == val){
            return head.next;
        }

        ListNode temp = head.next;
        ListNode pre = head;

        while(temp != null){
            if(temp.val == val){
                pre.next = temp.next;
                return head;
            }
            temp = temp.next;
            pre = pre.next;
        }

        return head;
    }

时间复杂度：O(n)
空间复杂度：O(1)

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def deleteNode(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if head == None:
            return None

        if head.val == val:
            return head.next

        temp = head.next
        pre = head

        while temp != None:
            if temp.val == val:
                pre.next = temp.next
                return head
            temp = temp.next
            pre = pre.next

        return head

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (head == nullptr) {
            return nullptr;
        }

        if (head->val == val) {
            return head->next;
        }

        ListNode* temp = head->next;
        ListNode* pre = head;

        while (temp != nullptr) {
            if (temp->val == val) {
                pre->next = temp->next;
                return head;
            }
            temp = temp->next;
            pre = pre->next;
        }

        return head;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteNode(head *ListNode, val int) *ListNode {
    /*
    :type head: ListNode
    :type val: int
    :rtype: ListNode
    */
    if head == nil {
        return nil
    }

    if head.Val == val {
        return head.Next
    }

    temp := head.Next
    pre := head

    for temp != nil {
        if temp.Val == val {
            pre.Next = temp.Next
            return head
        }
        temp = temp.Next
        pre = pre.Next
    }

    return head
}

JS

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
const deleteNode = (head, val) => {
    if(head === null){
        return null;
    }

    if(head.val === val){
        return head.next;
    }

    let temp = head.next;
    let pre = head;

    while(temp !== null){
        if(temp.val === val){
            pre.next = temp.next;
            return head;
        }
        temp = temp.next;
        pre = pre.next;
    }

    return head;
};

剑指offer题解

发表回复取消回复

后才能评论

mpweixin用户普通 2024年11月28日下午12:52

每一次判断下一个节点的值是不是等于val

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head.val == val:
            return head.next
        cur = head
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
                break
            cur = cur.next
        return head

Tom Yuan 普通 2024年11月21日上午9:36

前后指针的思路后一个摸到了那么把前一个的next指向后一个的next 来抠掉需要删除的node

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:

        # return null if head null
        if head == None:
            return None

        # handle found at head
        if head.val == val:
            head = head.next
            return head

        # handle else
        # if at last, then set to null (last.next)
        first = head
        second = head.next
        while first.next != None:
            if second.val == val:
                first.next = second.next
                return head
            first = first.next
            second = second.next

HU 普通 2024年3月2日上午5:36

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    // 设置哑节点
    const dummy = new ListNode(0);
    dummy.next = head;

    // 设置当前节点和前驱节点
    let pre = dummy;
    let cur = head;

    while(cur != null) {
        if(cur.val == val) {
            pre.next = cur.next;
        }
        cur = cur.next;
        pre = pre.next;
    }

    return dummy.next;
};

HU 普通 2024年3月2日上午5:34

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    // 设置哑节点
    const dummy = new ListNode(0);
    dummy.next = head;

    // 设置当前节点和前驱节点
    let pre = dummy;
    let cur = head;

    while(cur != null) {
        if(cur.val == val) {
            pre.next = cur.next;
        }
        cur = cur.next;
        pre = pre.next;
    }

    return dummy.next;
};

mpweixin用户普通 2023年7月8日下午10:40

代码实现
class linkelist:
def init(self, data):
self.data = data
self.next = None

class Solution:
def delete(self, head, val):

    if head == None:
        return None

    if head.data == val:
        return head.next

    temp = head.next
    pre = head

    while temp != None:
        if temp.data == val:
            pre.next = temp.next
            return head
        temp = temp.next
        pre = pre.next

    return head

Edison 普通 2022年10月23日下午6:44

我第一眼看到这道题的时候，以为只需要定义一个指向head的指针就好了。

但是如果定义一个指针的话，那么删除该节点以后，链表就不能完整的链接起来了。。。。

代码实现（cpp）

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        // 1.当链表头节点为空的情况
        if (head == nullptr) 
            return nullptr;

        // 2.如果头节点就是要删除的节点,那么就返回头节点的下一个节点
        if (head->val == val) 
            return head->next;
        else { // 3.由于head头结点已经在前面判断过了，所以直接从下一个点开始判断
            ListNode* cur = head; // cur用于保存头节点
            ListNode* curNext = head->next; // curNext保存头节点的下一个节点
            while (curNext != nullptr) { 
                if (curNext->val == val) { // 如果curNext节点的val等于要删除的val
                    cur->next = curNext->next; // 把cur的next链接到curNext的next
                    return head; // 返回head
                }
                curNext = curNext->next;
                cur = cur->next;
            }
        }
        return head;
    }
};

Monster Dump 普通 2022年10月22日下午7:34

代码实现 (Java)

    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode pre = head;
        ListNode curr = head.next;
        while (curr != null && curr.val != val) {
            pre = curr;
            curr = curr.next;
        }
        if (curr != null) {
            pre.next = curr.next;
        }
        return head;
    }

时间复杂度: O(n)
空间复杂度: O(1)

勾陈一普通 2022年10月22日下午7:16

class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
// 如果要删除头节点，直接返回head->next
if(head->val val)
return head->next;

    // 使用两个指针
    ListNode *cur = head;   // cur指针用于记录当前节点
    ListNode *pre = cur;    // pre指针用于记录之前节点
    while(cur)
    {
        if(cur->val == val)
        {
            pre->next = cur->next; // 将之前节点的next域指向当前指针的next域
            break;
        }

        // 遍历链表
        pre = cur;
        cur = cur->next;
    }
    return head;
}

};

波波_1936 普通 2022年10月22日下午4:50

 public ListNode deleteNode(ListNode head, int val) {
        if (head == null) return head;
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode res = node;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return res.next;
    }

时间复杂度 O(n) ,n为链表长度
空间复杂度为 O(1) 使用了额外的临时链表存储原数据

Y7n05h 普通 2022年10月22日下午2:18

C++ 题解

class Solution {
public:
    ListNode *deleteNode(ListNode *head, int val) {
        ListNode t(0);
        t.next = head;
        auto *cur = &t;
        while (cur->next) {
            auto *tmp = cur->next;
            if (tmp->val == val) {
                cur->next = tmp->next;
                return t.next;
            }
            cur = tmp;
        }
        return t.next;
    }
};

Y7n05h 普通 2022年10月22日下午2:18

C++ 题解

class Solution {
public:
    ListNode *deleteNode(ListNode *head, int val) {
        ListNode t(0);
        t.next = head;
        auto *cur = &t;
        while (cur->next) {
            auto *tmp = cur->next;
            if (tmp->val == val) {
                cur->next = tmp->next;
                return t.next;
            }
            cur = tmp;
        }
        return t.next;
    }
};

晨渊普通 2022年10月22日上午9:13

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head == NULL){  //如果为空
            return head;  
        }
        if(head->val == val ) {//如果只有一个头指针
            return head->next;
        }
         //找到删除点
         ListNode *temp,*pre;
         temp = head->next;
         pre = head;
         while(temp->val!= val){
              pre = temp;
             temp=temp->next;
         }
         if(temp==NULL) return head; //没有找到

         //删除节点
         pre->next = temp->next;
         return head;

    }
};

cute. 普通 2022年10月22日上午1:07

// 双指针
var deleteNode = function(head, val) {
    // 初始化哨兵节点(dummy),并指向head
    let dummy = new ListNode(0, head);
    let pre = dummy;
    // cur = dummy.next = head;
    let cur = head;
    while( cur !== null) {
        if(cur.val === val) {
            // 通过双指针的指向，删除与val相同的值
            pre.next = cur.next;
            break;
        }
        pre = cur;
        cur = cur.next;
    }
    return dummy.next;
};

时间复杂度:O(n)
空间复杂度:O(1)

Spermalow 普通 2022年10月21日下午10:35

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if (!head) return head;    
        if (head->val == val) return head->next;    // 如果删除的值为头结点，直接返回头节点下一个结点即可
        ListNode * currentNode = head;
        ListNode * nextNode = head->next;
        while (nextNode) {    // 由于head头结点已经在前面判断过了，所以直接从下一个点进行遍历
            if (nextNode->val == val) {    // 如果该点值与目标值一致，则使用该点的上一个结点进行“跳跃式指向”即可完成删除（可以画图理解）
                currentNode->next = currentNode->next->next;
            }
            // 两个指针都需要往后走一步
            currentNode = currentNode->next;
            nextNode = nextNode->next;
        }
        return head;
    }
};

🚲南下普通 2022年10月21日下午9:22

class Solution { //打卡，双指针
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val){
            return head->next;
        }
        ListNode* pre = head;
        ListNode* cur = head->next;
        while(cur->val!=val && cur->next!=nullptr){
            pre = cur;
            cur = cur->next;
        }
        if(cur!=nullptr){
            pre->next = cur->next;
        }
        return head;

    }
};

🚲南下普通 2022年10月21日下午9:20

class Solution { //打卡，双指针
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val){
            return head->next;
        }
        ListNode* pre = head;
        ListNode* cur = head->next;
        while(cur->val!=val && cur->next!=nullptr){
            pre = cur;
            cur = cur->next;
        }
        if(cur!=nullptr){
            pre->next = cur->next;
        }
        return head;

    }
};