【链表专题】剑指 Offer 18. 删除链表的节点
本问题对应课程链接：剑指offer刷题第四期
要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路，请代码不要直接抄袭复制我题解区给的代码哦。
2、给出你代码所用的时间复杂度和空间复杂度
第一次打卡注意：打卡的时候，代码支持 markdown 格式，并且必须要指定语言，比如
shuaidi shuaidi shuaidi shuaidi
共以下 84 个回答
【删除链表的节点】C++
打卡
打卡
、、、java
删除链表节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
}
递归，将等于输入值的节点替换成下一个节点返回，前一个节点指向返回的节点
“`python
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head is not None:
if head.val val:
head = head.next
else:
newhead = self.deleteNode(head.next,val)
head.next = newhead
return head
“`
/**
* 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){
return head->next;//返回头节点的后续节点
}
//******初始化******
ListNode* cur = head->next;
ListNode* pre = head;
//*****删除操作*****
while (cur != nullptr){
if (cur->val ){
pre->next = cur->next;//删除操作
return head;
}
//*****定位节点*****
cur = cur->next;
pre = pre->next;
}
return head;
};
时间O(n)
空间O(1)
第一次写的，稍微复杂了一点。注意1:头节点判空 2.最后一个节点是删除节点的情况可以被合并
第二次写的
/**
1.判断头节点是否是要删除的节点
2.使用快慢指针
slow := head
fast := head.Next
3 若fast nil 则返回head
4 若fast != nil 则通过fast遍历链表进行比对
若fast.Val val 则 slow.Next = fast.Nest 删除fast节点后跳出循环返回head，(此处fast节点置为nil是否有利于GC回收)
反之 fast = fast.Next, slow = slow.Next
5.跳出循环，没有找到要删除的节点，返回head
*/
func deleteNode(head *ListNode, val int) *ListNode {
if head nil {
return head
}
if head.Val val {
return head.Next
}
slow := head
fast := head.Next
}
时间复杂度 O(n)空间复杂度 O(1)”’c++
//打卡
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head nullptr){
return nullptr;
}
if(head->val val){
return head->next;
}
ListNode *dum = new ListNode(head->val);
dum->next = head;
head = dum;
ListNode *p = head;
ListNode *q = head->next;
while(q != nullptr){
if(q->val val){
p->next = q->next;
return head->next;
}
q = q->next;
p = p->next;
}
return head->next;
}
};
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 前驱节点 结果节点
ListNode pre =new ListNode();
ListNode result =pre;
pre.next = head;
while(head!=null)
{
if(head.valval)
{
pre.next=head.next;
head=pre.next;
return result.next;
}
pre=pre.next;
head=head.next;
}
return result.next;
}
}
“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
//head为空时
if(head == null) return null;
//删除的是头节点时
if(head.val == val) return head.next;
ListNode pre = head;
ListNode cur = head.next;
//循环遍历,直到找到要删除的节点
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next = cur.next;
return head;
}
}
//打卡
打卡：
“`c++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* current = head;
ListNode* pre = new ListNode();
while(current){
if(val == head->val){
head = head->next;
}
if (current->val == val){
pre->next = current->next;
current = nullptr;
break;
}else{
pre = current;
current = current->next;
}
};
“`
链表节点带
*和不带*后续代码书写有区别；首先对链表可能出现的特殊情况进行判断，然后循环链表找目标删除
时间复杂度：O(N)
空间复杂度：O(1)
维护一个当前指针的前置指针，将前置指针的next指向当前节点的next
时间复杂度on
空间复杂度o1
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.val val) return head.next;
ListNode pre = head;
ListNode cur = head;
while(cur != null && cur.val != val) {
pre = cur;
cur = cur.next;
}
if(cur != null) pre.next= cur.next;
return head;
}
}
估计也就我用TS写了
代码实现：
class linkelist:
def init(self, data):
self.data = data
self.next = None
class Solution:
def delete(self, head, val):
时间复杂度O(n)
空间复杂度O(1)
代码如下
代码如下
代码如下
时间复杂度:O(n)
只需要遍历一次整个链表
空间复杂度:O(1)
增加了一个临时指针变量
写一个dummyHead，next指向head，用于记录head的索引。然后用一个cur指针来进行遍历，后面符合条件的就是用两次next进行跳过，不满足条件的就直接遍历。
下面是C++ 代码
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val)
{
if (head->val val) return head->next;
ListNode* pre = head;
while (head->next->val != val) head = head->next;
head->next = head->next->next;
return pre;
}
};
ˋcpp//双指针
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head -> val val) return head -> next; //特例处理，删除第一个节点
ListNode *pre = head, *p = head -> next; //初始化
while(p != nullptr && p->val != val){ //定位：当p为空值或者等于val时跳出
pre = p;
p = p -> next;
}
if(p != nullptr){
pre -> next = p -> next;
free(p);
}//按照p所指节点的情况删除节点
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) {
ListNode *newhead = new ListNode(0);
newhead->next = head;
ListNode *cur, *next;
cur = newhead;
next = newhead->next;
while (cur != NULL && cur->next != NULL) {
next=cur->next;
if (next->val == val) {
cur->next = next->next;
// delete next;
cur = cur->next;
} else {
cur = cur->next;
}
}
return newhead->next;
}
};
“`
许久没写算法题了，代码可能写复杂了点，但最终也还是通过了
大概思路就是：
– 遍历到要删除节点的前一个节点，进行删除操作。链表中的删除操作，无非就是把指针指向进行修改，因此在修改指向前，要把原链表节点记录下来，否则节点会丢失。
– 另外，需要注意的就是删除的是头节点，则直接将头节点赋给下一个节点即可。
– 还有链表为空的情况。这种情况就没有可删除的了，直接返回空链表即可。
时间复杂度O(n)
采用双指针，主要判断头节点为null或只有一个头节点
不知道为啥markdown格式用不了，就将就一下吧。在此方法中，首先判断链表是否为空，空则输出空。不为空就进入下一步骤。对于不为空的链表，首先判断头节点是否为要删除的节点，若是则直接返回头节点的下一个节点head.next。接着定义当前节点和前置节点，遍历链表，查找要删除的节点，若找到则将前置节点的next指向当前节点的next，即删除节点。最后放回节点即可。本人为纯菜鸟，表达不顺的，请多多谅解。
时间复杂度O(n)
”’java
public ListNode deleteNode(ListNode head, int val) {
if(head null){
return null;
}
时间复杂度O(n)
时间复杂度：O(n)
”’
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(1);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if(cur->next->val val) {
cur->next = cur->next->next;
break;
} else {
cur = cur->next;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
}
};
”’
O(n) 双指针删除指定节点
空间：O1 时间On
“`c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteNode(struct ListNode* head, int val){
struct ListNode *p,*q;
if(head==NULL) return head;
if(head->val==val) return head->next;
p=head;
q=head->next;
while(q!=NULL)
{
if(q->val==val)
{
p->next=q->next;
return head;
}
p=p->next;
q=q->next;
}
return head;
}
//时间复杂度O（n）
//空间复杂度O(n)
双指针，O(n)
java
代码
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head null){
return null;
}
}
第一天
“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
}
`
“
剑指Offer 18.删除链表的节点
双指针法
时间复杂度：O（n）
// 打卡
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(-1, head);
ListNode fast = dummy.next;
ListNode slow = dummy;
while(fast != null){
if(fast.val val){
slow.next = fast.next;
break;
}
fast = fast.next;
slow = slow.next;
}
return dummy.next;
}
}
代码
public class Node {
Node next = null;
int data;
public Node(int data){
this.data=data;
}
}
public Node deleteNode(Node head,int val){
Node pre=head;
Node cur=pre.next;
while (cur!=null && cur.data!=val){
pre=cur;
cur=cur.next;
}
if (cur.dataval)pre.next=cur.next;
return head;
}
时间复杂度O（n）
空间复杂度O(n)
Time Complexity: O(n) 最糟糕情况删除尾节点走一遍
Space: O(1)
代码
下面是代码
下面是代码
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
};
时间复杂度O（n）
空间复杂度O（1）
“`c++
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
};
“`
时间复杂度O(n)
空间复杂度O(1)
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(headnull) return head;
ListNode dummyNode = new ListNode(0); //建立虚拟节点
dummyNode.next = head;
ListNode pre = dummyNode;
while(head != null && head.val != val){
pre = pre.next;
head = head.next;
}
pre.next = head.next;
return dummyNode.next;
}
}
“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head.val == val) return head.next;
ListNode cur = head;
ListNode pre = head;
while(cur!=null){
if(cur.val == val){
pre.next = cur.next;
break;
} else{
pre = cur;
cur = cur.next;
}
}
return head;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public ListNode deleteNode(ListNode head, int val) { // 定义了一个方法，用于删除单链表中指定数值的节点
if(head null){ // 如果头节点为空，直接返回null
return null;
}
}
空间复杂度：O(1)
时间复杂度：O(n)
时间复杂度：O(n)
空间复杂度：O(1)
时间复杂度 O(N) 空间复杂度 O(1)
时间复杂度：O(N)
空间复杂读：O(1)
“`python
第一题打卡
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:
slow = ListNode(-1)
fast = head
newhead = slow
while fast:
if fast.val != val:
slow.next = fast
slow = slow.next
fast = fast.next
slow.next = None
return newhead.next
执行用时：
8 ms
内存消耗：
9.1 MB
通过测试用例：
37 / 37
/**
* 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(headNULL) return NULL;
if(head->valval)return head->next;
ListNode* temp=head->next;
ListNode* pre=head;
};
试试
思路：用虚拟头节点减少判断，两个指针指向 前后两个节点 然后按顺序遍历，当后节点的值为目标值，则把前节点指向后节点的下一个节点，最后的链表头节点固定是 虚拟头节点指向的下一个节点
1.思路：先找出头指针为空的情况，当头指针的值为要删除的节点值，返回头结点的下一个指针，定义双指针p，q，p比q快一位，p指向的值为要删除的节点值时，将q的下一位指向p的下一位，返回head。
2.时间复杂度O（n）
空间复杂度O（1）
时间复杂度：O(n)
空间复杂度：O（1）
时间复杂度:O(n)
空间复杂度:O(1)
时间复杂度：O（n）
空间复杂度：O（1）
思路：保持head结点不动，重新定义一个结点初始指向头结点。因为要删除指定值的节点所以我们需要该结点指向要删除节点的上一个结点，所以判断该结点的下一个结点的val值是不是要删除的节点。是就跳出循环，不是就将结点指向下一个节点位置。如果找到了将该结点指向下下一个节点。
需要特判的是head结点的val值是不是要删除的结点，此时头结点需要更新。
它说评论必须包含中文。