control 普通 2024年12月6日下午3:16

1: 建立辅助头节点的习惯
2: 删除节点的做法是 node-> node1 -> node2 , 调整后是。node->node2 ; 也就是 node.next -> node2

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode tmpHead = new ListNode();
        tmpHead.next = head;
        ListNode preNode = tmpHead;
        ListNode curNode = preNode.next;
        while(curNode != null){
            if( curNode.val == val ){
                preNode.next = curNode.next;
                break;
            }
            preNode = curNode;
            curNode = curNode.next;
        }
        return tmpHead.next;
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午1:47

/**
解题思路：
判断当前指针p的下一个元素位置是否为val，如果是，则p.next指向p的下下个元素完成删除，
第一个元素也可能被删除，所以p初始指向哨兵指针dummy, dummy.next = head即可

复杂度分析：
只遍历一次链表，时间复杂度O(N)
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null){
            return null;
        }

        ListNode dummy = new ListNode(-1, head);
        ListNode p = dummy;

        while (p != null && p.next != null){
            if (p.next.val == val){
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }

        return dummy.next;

    }
}

0 赞同 0 条回复

吃碗草莓豆沙普通 2024年11月29日下午3:34

“`C++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
//head为null，直接返回
if(head == nullptr){
return nullptr;
}
//head的值为要删除节点的值，返回头节点的下一个节点
if(head->val == val){
return head->next;
}
//指针循环判断，找到指定节点值并删除返回head
ListNode *cur = head;
while(cur->next != nullptr && cur->next->val != val){
cur = cur->next;
}
//找到指定节点，执行当前节点的.next等于当前节点的.next.next实现删除目标节点操作
if(cur->next != nullptr){
cur->next = cur->next->next;
}
//返回头节点
return head;
}
};

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

0 赞同 0 条回复

宇晴普通 2024年11月28日下午9:16

js解法

var deleteNode = function(head, val) {
    if (head.val === val) {
        return head.next
    }
    head.next = deleteNode(head.next, val)
    return head
};

0 赞同 0 条回复

泽阳普通 2024年11月28日上午10:20

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


class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1, head);
        ListNode prev = sentinel;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                break;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }

        return sentinel.next;
    }
}

0 赞同 0 条回复

為愛而生普通 2024年11月26日下午11:21

时间0ms 内存42.95MB

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode cur, pre;
pre = head;
cur = head.next;
if (pre.val val) {
head = cur;
cur = cur.next;
pre = head;
return head;
} else
while (cur != null) {
if (cur.val val) {
pre.next = cur.next;
cur = cur.next;
}else{
pre = pre.next;
cur = cur.next;
}
}
return head;
}
}

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月26日下午4:27

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
//特例化处理，头节点head.val = val
if(head.val == val)
return head.next;
//定义pre头节点查找，cur为下一节点
ListNode pre = head, cur = head.next;
while(cur != null && cur.val != val){
//循环查找
pre = cur;
cur = cur.next;
}
//如果cur为空，则说明查找值不存在
if(cur != null) pre.next = cur.next;
return head;
}
}
“`

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月25日下午5:54

“`python
class Solution(object):
def deleteNode(self, head, val):
//头节点是要删除的节点，直接从下一个节点返回
if head.val==val:
return head.next
//初始化两个指针
pre=head
cur=head.next
//后边的指针不为空或者值不是要找的值时，继续寻找
while cur and cur.val!=val:
pre=cur
cur=cur.next
//找到值后进行删除
if cur:
pre.next=cur.next
//返回删除后的结果
return head
时间复杂度：O(N) N为链表长度
空间复杂度：O(1) 两个指针占用常数大小空间

0 赞同 0 条回复

Aatorx 永久会员 2024年11月25日下午3:00

“`C++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
* 先处理特殊情况，若链表为空，返回NULL
if(head == NULL){
return head;
}
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;
}
pre = temp;
temp = temp->next;
}
return head;
}
};
“`
需要遍历长度为n的链表，时间复杂度为O(n)，不需要额外空间，空间复杂度为O(1)。

0 赞同 0 条回复

rr 普通 2024年11月25日上午11:31

##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):
“””
删除链表中值为 val 的节点

    :param head: ListNode, 链表的头节点
    :param val: int, 需要删除的节点的值
    :return: ListNode, 删除目标节点后的链表头节点
    """
    # 处理空链表的情况
    if head is None:
        return None

    # 如果头节点是需要删除的节点，直接返回下一个节点
    if head.val == val:
        return head.next

    # 初始化指针：prev 指向前驱节点，curr 指向当前节点
    prev = head
    curr = head.next

    # 遍历链表，寻找目标节点
    while curr is not None:
        if curr.val == val:
            # 跳过目标节点
            prev.next = curr.next
            return head
        # 向前移动指针
        prev = curr
        curr = curr.next

    # 未找到目标节点，返回原链表
    return head

在最坏情况下，需要遍历整个链表以找到目标节点。例如，目标节点是最后一个节点或者不存在。
链表长度为 𝑛，因此时间复杂度为 𝑂(𝑛)。
代码中没有使用额外的数据结构或递归，所有操作在输入链表上进行，空间复杂度主要由指针 pre 和 curr 占用。
因此，空间复杂度为 𝑂(1)

0 赞同 0 条回复

LovLe 普通 2024年11月23日下午9:10

# 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]:
        pre=ListNode()
        pre.next=head
        cur=head
        if head==None:
            return head
        if head.val==val:
            return head.next    #引入虚拟头节点
        while cur.val != val :
            pre=cur
            cur=cur.next
        pre.next=cur.next
        return head #原始头节点，如果头节点匹配了呢，被去掉，所以这里分开写条件

思路更加完善：

头节点是否匹配，会被删除–> 返回头节点的下一个节点
当前cur节点不为空？是否遍历到val节点
- 判断cur节点不为空，那么就是遍历到了该节点，删除cur节点操作
- 不管遍历到了没有，最后返回头节点

# 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      #直接删去头节点，返回下一个节点
        pre,cur=head,head.next  
        while cur and cur.val!=val: # 要判断cur不为空，没有遍历到链表末尾还没找到
            pre=cur
            cur=cur.next
        if cur: pre.next=cur.next       #如果是cur不为空，那么一定是遍历到了val的节点，进行删除操作；否则不处理；最后返回头节点
        return head

虚拟头节点：

记住这个模板，使用虚拟头节点时，返回虚拟头节点的下一个

# 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]:
        dummyhead=ListNode(next=head)
        pre,cur=dummyhead,dummyhead.next    #初始化的时候，pre为虚拟头节点，cur为头节点；这样，当head.val匹配时，可以直接删去head（无差别删除）
        while cur and cur.val!=val:
            pre=cur
            cur=cur.next
        if cur: pre.next=cur.next
        return dummyhead.next   #返回虚拟头节点的下一个

时间复杂度：O(n)
空间复杂度：O(1) 额外使用了虚拟头节点和两个指针

0 赞同 0 条回复

无言永久会员 2024年11月23日下午4:30

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *dummy = new ListNode();
        dummy->next = head;
        ListNode *pre = dummy;
        ListNode *cur = dummy->next;
        while(cur) {
            if(cur->val == val) {
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        head = dummy->next;
        return head;  
    }
};
//时间复杂度: O(n)
//空间复杂度: O(1)

0 赞同 0 条回复

借来的猫普通 2024年11月23日上午10:36

class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(headnull) return null;
if(head.valval) return head.next;
ListNode cur=head.next;
ListNode pre=head;
while(cur.val!=val&&cur!=null){
pre=pre.next;
cur=cur.next;
}
if(cur!=null)pre.next=cur.next;
return head;
}
}
时间复杂度O(n)，空间复杂度：O(1)

0 赞同 0 条回复

岱永久会员 2024年11月21日下午11:22

1.没用双指针，直接p.next; 但注意头节点要另外考虑
2.代码
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode p = head;
if(head.val val)return head.next;
while(p.next != null){
if(p.next.val val){
p.next = p.next.next;
}else{
p=p.next;
}
}
return head;
}

}

0 赞同 0 条回复

yelinliner 普通 2024年11月21日下午10:08

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 1.特殊情况
        if(head==null){
            // 链表为空
            return null;
        }
        if(head.val==val){
            // 链表的第一个即查找（删除）值
            return head.next;
        }
        // 2.双指针 查找并删除节点
        ListNode cur=head.next;
        ListNode pre=head;
        while(cur!=null){
            // cur用于遍历查找，pre用于删除返回
            if(cur.val==val){
                pre.next=cur.next;
                return head;
            }
            cur=cur.next;
            pre=pre.next;
        }
        return head;
    }
}

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

0 赞同 0 条回复

打豆豆啊打豆豆普通 2024年11月21日下午9:55

思路如下：
1、异常判断：
1.1 头指针为空，则直接返回空；
1.2 头指针的值为目标值，则返回头节点的下一节点；
2、循环判断：
2.1 定义一个指针用来移动；
2.2 进入循环，思考退出循还逻辑：条件1：遍历所有节点至当前节点的.nex为空，条件2：当前节点的.next的.val不为目标值；
2.3 循环中，当前节点指向下一节点；
3 若当前节点.next不为空，则当前节点的.next等于当前节点的.next.next，即删除目标节点；
4 返回头指针

“`C++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head == nullptr) return nullptr;
if(head->val == val) return head->next;
ListNode *cur = head;
while(cur->next != nullptr && cur->next->val != val)
{
cur = cur->next;
}

    if(cur->next !=nullptr) cur->next = cur->next->next;

    return head;
}

};

“`

1 赞同 0 条回复

爱姆露普通 2024年11月21日下午8:52

首先分情况，头节点为空，头节点值为val，头节点值不为val，前两种很简单，直接return ，第三种，需要两个节点指针，使用两个指针 cur 和 prev，分别指向当前节点和前一个节点。
遍历链表，直到找到要删除的节点。
如果找到了要删除的节点（即 cur->val val），将前一个节点的 next 指针指向当前节点的下一个节点，从而删除当前节点。
如果遍历完链表没有找到要删除的节点，返回原链表头节点。
if (head nullptr) {
return nullptr;
}

// 如果头节点就是要删除的节点
if (head->val val) {
return head->next;
}

ListNode* cur = head;
ListNode* prev = nullptr;

while (cur != nullptr) {
    if (cur->val == val) {
        // 删除当前节点
        if (prev != nullptr) {
            prev->next = cur->next;
        }
        return head;
    }
    prev = cur;
    cur = cur->next;
}

return head;

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月21日下午8:39

思路：指针为空和至少一个节点链表的首个节点符合条件，以及删除节点在链表中间需要删除的情况
利用双指针使得在找到删除节点时找到前驱，从而减少重新遍历的时间
答案：
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head==null){
            return null;
        }
        else 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)

0 赞同 0 条回复

橙子陈爱吃橙子普通 2024年11月21日下午7:30

class Solution {
    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;
            }
            pre = pre.next;
            temp = temp.next;
        }
        return head;
    }
}

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

0 赞同 0 条回复

桃桃摇摇奶昔° 普通 2024年11月21日下午1:59

class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head.valval){return head.next;}
if (headnull){return null;}
ListNode p = head;
ListNode temp = head.next;
while(temp != null){
if (temp.val val){
p.next=temp.next;
return head;
}
temp=temp.next;
p=p.next;
}
return head;
}
}
时间复杂度O（n），空间复杂度：O(1) —— 仅使用了常数额外空间。

0 赞同 0 条回复

捕风永久会员 2024年11月21日下午12:20

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
//先解决特殊情况：是否为空指针、是否为头节点
//如果遍历到空指针
if(head null){
return null;
}

//如果删除的是头节点
if(head.val == val){
    return head.next;
}

ListNode temp = head.next; //temp表示要删除的结点
ListNode pre = head; //pre永远指向temp 的前一个节点，用于修改链表指针以删除目标节点

while(temp != null){
    // 如果找到，直接删除，返回
    if(temp.val == val){
        pre.next = temp.next;
        return head;
    }
    temp = temp.next; // 如果没有找到，继续下一个
    pre = pre.next;
}

return head;

}

}
时间复杂度：O(n) —— 最多遍历链表中的 n 个节点。
空间复杂度：O(1) —— 仅使用了常数额外空间。

0 赞同 0 条回复

zing 普通 2024年11月21日上午11:37

链表结点的思考：
链表结点包含两个域，一个数据域一个指针域。其中指针域在代码实现时保存的是下一个结点，来实现“指针”的功能。

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: 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
        if cur: pre.next = cur.next
        return head

解法二：设置头结点，一般化

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head == None:    return head
        dummy = ListNode(0, head)

        pre, cur = dummy, dummy.next
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        if cur: 
            pre.next = cur.next
        return dummy.next

0 赞同 0 条回复

Renasc 普通 2024年11月21日上午10:11

通过设置虚拟头结点来进行遍历

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

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = dummy.next;

        while (curr != null) {
            if (curr.val == val) {
                    prev.next = curr.next;
            }
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

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

前后指针的思路后一个摸到了那么把前一个的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

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午9:22

题解思路：
本题的要求是从链表中删除特定值的节点。为了简化操作，我们可以引入一个虚拟的头节点，把它指向真实的链表头。这样，无论删除的是头节点还是其他节点，我们都可以从虚拟头节点开始遍历。
在遍历过程中，我们使用一个指针检查每个节点的下一个节点的值。如果该值等于目标值，我们就调整当前节点的 next 指针，跳过要删除的节点。否则，我们将指针移动到下一个节点，继续检查。
遍历结束后，新链表的头节点是虚拟头节点的 next 指针所指向的节点。
最后，别忘了释放虚拟头节点的内存。

参考代码：

“`c++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
// 创建一个虚拟头节点，用于处理删除头节点的情况
ListNode* dummyHead = new ListNode();
dummyHead->next = head;

    // 当前节点初始化为虚拟头节点
    ListNode* cur = dummyHead;

    // 遍历链表，直到当前节点的下一个节点为空
    while (cur->next != nullptr) {
        // 如果下一个节点的值等于要删除的值
        if (cur->next->val == val) {
            // 通过跳过下一个节点来删除它
            cur->next = cur->next->next;
        } else {
            // 如果值不等于，继续移动到下一个节点
            cur = cur->next;
        }
    }

    // 获取新的头节点（即删除操作后的链表头）
    ListNode* newHead = dummyHead->next;
    // 释放虚拟头节点的内存
    delete dummyHead;
    // 返回新的链表头
    return newHead;
}

};

“`

时空分析：
首先，时间复杂度方面，由于我们需要遍历链表中的每个节点一次，检查并删除符合条件的节点。因此，时间复杂度为 O(n)，其中 n 是链表中节点的总数。这是因为我们可能需要对每个节点进行一次访问。
其次，空间复杂度方面，我们使用了一个虚拟头节点来帮助处理删除操作，但这个虚拟节点的空间消耗是常量级的。除了指针外，没有使用额外的空间来存储其他数据。因此，空间复杂度为 O(1)。
综上所述，该算法的时间复杂度是 O(n)，而空间复杂度是 O(1)。

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午9:14

打卡

“`c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head == nullptr){
return nullptr;
}
if(head->val == val){
return head->next;
}
ListNode* node = head->next;
ListNode* pre = head;
while(node !=nullptr){
if(node->val == val){
pre->next = node->next;
return head;
}
node = node->next;
pre = pre->next;

    }

return head;

}


};
“`

0 赞同 0 条回复

jaron 普通 2024年11月21日上午8:52

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

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        ListNode last = head;
        ListNode cur = null;
        while (last.next != null) {
            cur = last.next;
            if (cur.val == val) {
                last.next = cur.next;
                break;
            }
            last = cur;
        }
        return head;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午2:07

“`java
18.删除链表的节点
class Solution {
public ListNode deleteNode(ListNode head, int val) {

    if(head==null) return null;
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode cur = dummy;
    while(cur.next!=null){
        if(cur.next.val ==val){
            cur.next = cur.next.next;
            break;
        }
        else cur = cur.next;
    }
    return dummy.next;

}
}

0 赞同 0 条回复

Rad 普通 2024年11月21日上午1:26

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
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）

0 赞同 0 条回复

咕普通 2024年11月20日下午11:23

class Solution:
    def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head.val == val:
            return head.next

        pre, cur = head, head.next
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        if cur:
            pre.next = cur.next

        return head

时间复杂度 O(N) 空间复杂度 O(1)

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月20日下午10:58

“`java
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val) return head.next;
ListNode pre = head, cur = head.next;//双指针
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next = cur.next;
return head;
}
}

0 赞同 0 条回复

ㅤ 普通 2024年11月20日下午10:49

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head null) {
// 如果头节点为空,则直接返回空
return null;
}

    if (head.val == val) {
        // 头节点为目标节点,则直接返回下一个
        return head.next;
    }

    // 设置头节点为当前节点,进行遍历
    ListNode current = head;
    while (current.next != null) {
        if (current.next.val == val) {
            // 跳过需要删除的节点
            current.next = current.next.next;
            break; // 退出循环
        }
        current = current.next;
    }
    return head;

}

}

0 赞同 0 条回复

时光烙印普通 2024年11月20日下午10:33

删除链表的节点:
class Solution:
def deleteNode(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if head.val val: return head.next;
pre,cur = head,head.next
while cur and cur.val != val:
pre,cur = cur,cur.next
if cur: pre.next = cur.next
return head

0 赞同 0 条回复

陆狗陆狗普通 2024年11月20日下午10:31

题解

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head==null){
            return head;
        }
        // 【错误点2】
        if(head.val==val){
            return head.next;
        }
        ListNode pre=head;
        ListNode next=head.next;
        while(next!=null){
            if(next.val==val){
                 // 【错误点1】
                // 删除当前节点
                pre.next=next.next;
                return head;
            }else{
                // 下个节点
                pre=next;
                next=next.next;
            }
        }
        return head;
    }
}

错误点1 删除当前节点没有return，导致死循环。
错误点2 头结点删除后没有争取return

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月20日下午10:14

看了guide哥前面的讲解，试了下使用辅助头节点，果然少了很多判断，打开了新思路

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode node = new ListNode();
        node.next = head;
        ListNode newHead = node;
        while(node.next != null){
            if(node.next.val == val){
                node.next = node.next.next;
                break;
            }
            node = node.next;
        }
        return newHead.next;
    }
}

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

0 赞同 0 条回复

biangbb 普通 2024年11月20日下午10:14

“`java
//答案
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode p=new ListNode();
p.next=head;
ListNode pp=p;
while(p.next!= null){
if(p.next.val==val){
p.next=p.next.next;
break;
}else{
p=p.next;
}
}
return pp.next;
}
}

0 赞同 0 条回复

lQl 永久会员 2024年11月20日下午10:08

java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode cur = head;
        if(cur.val==val){
            return head.next;
        }
        while(cur.next!=null&&cur.next.val!=val){
            cur=cur.next;
        }
        cur.next=cur.next.next;
        return head;
    }
}

0 赞同 0 条回复

C。普通 2024年11月20日下午9:56

思路
先判断是否为空
if(head null){
return null;
}
再判断删除的是否为头节点
if(head.val val){
return head.next;
}
新建前节点和临时节点
ListNode temp = head.next;
ListNode pre = head;
临时节点不为空，循环寻找目标值的节点
找到则将前节点的next指向临时节点的next，跳过temp节点完成删除操作
如果当前节点的值不等于 val，则将 temp 和 pre 指针都向前移动一个节点，继续检查下一个节点。
while(temp != null){
if(temp.val val){
pre.next = temp.next;
return head;
}
temp = temp.next;
pre = pre.next;
}

    return head;
}

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)

0 赞同 0 条回复

Pendulumpal 普通 2024年11月20日下午9:48

Code Block Example

C++ Implementation


// C++ Implementation
ListNode* deleteNode(ListNode* head, int val) {
    ListNode* p=new ListNode(0,head);
    while(p->next){
        if(p->next->val==val){
            ListNode* temp=p->next;
            p->next=temp->next;
            temp->next=nullptr;
            break;
        }
        p=p->next;
    }
    return (head->next)?head:p->next;
}

Java Implementation


// Java Implementation
public ListNode deleteNode(ListNode head, int val) {
    if(head.val==val)return head.next;
    ListNode pre=head;
    ListNode cur=head.next;
    while(cur!=null){
        if(cur.val==val){
            pre.next=cur.next;
            break;
        }
        pre=pre.next;
        cur=cur.next;
    }
    return head;
}

0 赞同 0 条回复

晓宇普通 2024年11月20日下午9:38

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode deleteNode(ListNode* head, int val) {
ListNode new_head, *p = &new_head, *q;
new_head.next = head;

    while(p->next){
        if(p->next->val == val){
            q = p->next;
            p->next = p->next->next;
            delete(q); // 为啥free时报错
            return new_head.next;
        }
        p = p->next;
    }
    return new_head.next;
}

};

1 赞同 0 条回复

越努力越幸运普通 2024年11月20日下午9:34

“`C++
class Solution
{
public:
ListNode* deleteNode(ListNode* head, int val)
{
if(nullptr == head)
{
return nullptr;
}

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

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

};

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

0 赞同 0 条回复

生活在经验里普通 2024年11月20日下午9:19

func deleteNode(head *ListNode, val int) *ListNode {
// 链表为空
if head nil {
return nil
}

// 头节点为待删除节点
if head.Val == val {
    return head.Next
}

// 双指针
cur := head
var prev *ListNode = head
for {
    // 链表中没有待删除节点
    if cur == nil {
        return head
    }

    if cur.Val == val {
        prev.Next = cur.Next
        cur.Next = nil
        return head
    }
    prev = cur
    cur = cur.Next
}

}

0 赞同 0 条回复

. 普通 2024年11月20日下午9:05

感觉java要忘光了（）时间O(n),空间O(1)
思路：先把空和只有一个元素的情况单独写出来，然后对于长度大于等于二的，设置两个指针分别指向前一个和当前指向的元素。当前一个元素不为要删除的元素时，继续遍历，直到当前元素为要删除元素。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head null){
return head;
}
else if(head.val val){
return head.next;
}

    ListNode pre = head;
    ListNode current = head.next;
    while(pre.val != val){
        if(current.val == val){
            pre.next = current.next;
            return head;
        } 
        pre = pre.next;
        current = current.next;
    }
    return head;
}

}

0 赞同 0 条回复

Firefly 普通 2024年11月20日下午9:02

代码：
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val)
{
for(auto p=head,q=head;p!=nullptr;q=p,p=p->next)
{
if(p->valval)
{
if(phead)
{
return p->next;
}
else
{
q->next= p->next;
break;
}
}
}
return head;
}
};

0 赞同 0 条回复

Jerry 普通 2024年11月20日下午8:52

时间o(n)
空间o(1)

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head == nullptr) return head;
        ListNode* myhead = new ListNode(-1, head);
        ListNode* pre = myhead;
        ListNode* cur = head;
        while(cur){
            if(cur->val == val){
                pre->next = cur->next;
                break;
            }
            cur = cur->next;
            pre = pre->next;
        }
        return myhead->next;
    }
};

0 赞同 0 条回复

momo 普通 2024年11月20日下午8:52

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 None:
return head
dummy = ListNode(1)
dummy.next = head
cur = dummy
while(cur.next):
if cur.next.val val:
cur.next = cur.next.next
break
else:
cur = cur.next
return dummy.next
不加break会报错

0 赞同 0 条回复

Xiang. 永久会员 2024年11月20日下午8:51

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(headnull) return null;
if(head.valval) return head.next;
ListNode tmp=head;
while(tmp.next!=null&&tmp.next.val!=val){
tmp=tmp.next;
}
if(tmp.next!=null){
tmp.next=tmp.next.next;
}
return head;
}
}

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

0 赞同 0 条回复

🌟 普通 2024年11月20日下午8:47

o(n)
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return nullptr;//空链表
ListNodeq=head;
ListNodecurrent=q->next;
if(q->valval){
//delete q;
return current;
}
while(current!=nullptr){
if(current->valval){
q->next=current->next;
// delete current;
break;
}else{
q=current;
current=current->next;
}
}
return head;
}
};

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:40

代码：
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* pre = head;
while(pre->val val){
if(pre->next != NULL){
pre = pre->next;
}
else{
return NULL;
}
}
ListNode* result = pre;
ListNode* p = pre->next;
while(p != NULL){
if(p->val val){
pre->next = p->next;
}
pre = p;
p = p->next;
}
return result;
}
};
思路：
先处理头结点，随后从头结点下一位开始遍历链表：设pre追踪节点上一位，遇到需要删除的值，将pre的next指向被删除节点的下一位。

时间复杂度O(n)，空间复杂度O(0)。

0 赞同 0 条回复

Carry on 普通 2024年11月20日下午8:39

class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 如果链表为空，返回空
if (head null) {
return null;
}
// 特殊情况: 删除的是头节点
if (head.val val) {
return head.next;
}
// 遍历链表，找到要删除的节点
ListNode current = head;
while (current.next!= null) {
if (current.next.val val) {
// 找到要删除节点，跳过它
current.next = current.next.next;
return head;
}
current = current.next;
}
// 如果没有找到目标节点，返回原链表
return head;
}
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:37

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy=new ListNode(-1,head),p=dummy;
        while(p.next!=null && p.next.val!=val){
            p=p.next;
        }
        p.next=p.next.next;
        return dummy.next;
    }
}

时间复杂度O(n),空间复杂度O（1）

0 赞同 0 条回复

parsons 普通 2024年11月20日下午8:24

class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
//1.头节点为删除点，直接返回next
if(head->val val)
return head->next;
//2.定义pre节点
ListNodepre = head;
//3.定义cur节点
ListNodecur = head->next;
//4.如果没检测到删除节点以及cur没到链表末尾
while(cur->val != val && cur != nullptr){
//5.两个节点继续向右遍历
pre = cur;
cur = cur->next;
}
//6.如果cur没到链表末尾，那么检测到了val,进行删除操作
if(cur != nullptr)
pre->next = cur->next;

    //7.返回节点
    return head;
}

};
时间复杂度 O(N)
空间复杂度 O(1)

0 赞同 0 条回复

Kisara 普通 2024年11月20日下午8:23

““java
只使用一个p节点，若head 相等直接删除，若之后找到，直接p.next=p.next.next跳过这个节点，不会导致空指针，while里面判断过p.next 不为空

class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.valval) return head.next;

    ListNode p = head;
    while(p.next!=null&&p!=null){
        if(p.next.val==val){
            p.next=p.next.next;
            return head;
        }
        p=p.next;
    }
    return head;
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:20

a.思路分析：
1.首先定义一个虚拟节点，目的是方便统一处理头节点和其他节点的删除逻辑。
2.定义一个探索指针cur用来寻找目标值。
3.当cur->next探索到目标值时，将cur的next指针指向下下个节点。
4.当删除完毕后，返回虚拟节点的下一个节点（因为虚拟节点在输入中是不存在的)。
b.代码：

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head == nullptr) return nullptr;
        ListNode* dummyHead = new ListNode();
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->val!=val)
        {
            cur = cur->next;
        }
        if(cur->next) cur->next = cur->next->next;

    return dummyHead->next;
}
};

c.当前代码的时间复杂度为o(n)，其中n是链表的长度；空间复杂度为o(1)，额外使用了常数级的内存。

0 赞同 0 条回复

月下足迹普通 2024年11月20日下午8:13

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if (head null) {
return null;
}

    // 如果要删除的是头节点
    if (head.val == val) {
        return head.next; // 直接返回下一个节点作为新的头节点
    }

    // 遍历链表找到要删除的节点的前一个节点
    ListNode current = head;
    while (current.next != null && current.next.val != val) {
        current = current.next;
    }

    // 如果找到了目标节点
    if (current.next != null) {
        current.next = current.next.next;
    }

    return head; // 返回链表的头节点
}

}

0 赞同 0 条回复

🍊 普通 2024年11月20日下午8:07

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.val val) return head.next;
ListNode p = head, q = p.next;
while(q.val != val){
p = p.next;
q = q.next;
}
p.next = q.next;
return head;
}
}
直接遍历

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午8:04

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;

        while (cur != null && cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

创建了虚拟头节点，是为了统一链表节点的操作；遍历链表，找到待删除节点的前驱节点（我只使用了一个变量来表示，可以再使用一个变量 pre 来表示前一个节点），即 cur.next == val 时，说明 cur 就是待删除节点的前驱节点，进行删除操作：cur.next = cur.next.next，从而跳过 cur.next 这个节点。最后返回删除节点后的链表头节点 dummy.next。

时间复杂度：O(n)，需要遍历整个链表一次。
空间复杂度：O(1)，只使用了常数级的额外空间。

1 赞同 0 条回复

苯庸普通 2024年11月20日下午8:03

class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead, cur = head;
while(cur.val != val){
pre = pre.next;
cur = cur.next;
}
pre.next = cur.next;
return dummyHead.next;
}
}
思路：用个虚拟头节点来方便处理第一个元素就是要删除的情况，然后依次遍历到要删除的元素，将要删除的元素的前一个元素连接到其后一个元素，删除完成。
时间复杂度 o(n)
空间复杂度 o(1)

0 赞同 0 条回复

黑键〰普通 2024年11月20日下午8:02

/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val=undefined ? 0 : val)
* this.next = (next=undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var deleteNode = function(head, val) {
let dummy = new ListNode(0, head)
let pre = dummy
let p0 = head
while(p0 ! null) {
if(p0.val = val) {
pre.next = p0.next
break
}
pre = p0
p0 = p0.next
}
return dummy.next
};
时间复杂度O(N)
空间O(1)

0 赞同 0 条回复

【链表专题】剑指 Offer 18. 删除链表的节点

共以下 59 个回答

C++ Implementation

Java Implementation

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题取消回复

【链表专题】剑指 Offer 18. 删除链表的节点

共以下 59 个回答

C++ Implementation

Java Implementation

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题 取消回复

# 回答此问题取消回复