给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。
1.此题对比原题有改动
2.题目保证链表中节点的值互不相同
3.该题只会输出返回的链表和结果做对比,所以若使用 C 或 C++ 语言,你不需要 free 或 delete 被删除的节点
数据范围:
0<=链表节点值<=10000
0<=链表长度<=10000
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。
{2,5,1,9},5
{2,1,9}
给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 2 -> 1 -> 9
{2,5,1,9},1
{2,5,9}
给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 2 -> 5 -> 9
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @param val int整型 # @return ListNode类 # class Solution: def deleteNode(self , head: ListNode, val: int) -> ListNode: # write code here if not head:return 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
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param val int整型 * @return ListNode类 */ ListNode* deleteNode(ListNode* head, int val) { // 时间复杂度O(N),空间复杂度O(1) ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; while (head->next) { if (head->next->val == val) { head->next = head->next->next; break; } head = head->next; } return dummy->next; } };
class Solution: def deleteNode(self , head: ListNode, val: int) -> ListNode: # 删除结点为头结点 if head.val == val: return head.next # 设置两个结点p1、p2:p1是删除结点p2的前一个结点 p1 = head p2 = head.next while p2.val != val and p2: p2 = p2.next p1 = p1.next else: p1.next = p2.next return head
public class Solution { public ListNode deleteNode (ListNode head, int val) { if(head == null) return null; ListNode p1 = head, p2 = head.next; if(head.val == val) return head.next; //这里考虑到了删除的结点不在链表里 while(p2 != null){ if(p2.val != val){ p1 = p1.next; p2 = p2.next; }else{ p1.next = p2.next; return head; } } return null; } }
public class Solution { public ListNode deleteNode (ListNode head, int val) { // 链表结点数量为【0,10000】,因此可能为空链表,这时候直接返回空 if(head == null) return head; ListNode dummy_node = new ListNode(0); dummy_node.next = head; ListNode pre = dummy_node, cur = head; // 如果为目标值,跳过这个结点,同时,由于节点的值都是不相同的,因此删除后直接break; // 否则继续向后寻找 while(cur != null){ if(cur.val != val){ pre = cur; cur = cur.next; } else{ pre.next = cur.next; break; } } return dummy_node.next; } }
struct ListNode* deleteNode(struct ListNode* head, int val ) { struct ListNode* L = (struct ListNode* )malloc(sizeof(struct ListNode)); L->next = head; struct ListNode* p = head; struct ListNode* pre = L; while(p) { if(p->val == val) { p = p->next; pre->next = p; } else { p = p->next; pre = pre->next; } } return L->next; }
class Solution: def deleteNode(self , head: ListNode, val: int) -> ListNode: # write code here vHead = ListNode(-1) vHead.next = head cur = vHead while cur.next: if cur.next.val == val: cur.next = cur.next.next break cur = cur.next return vHead.next看着需要判断头结点的不太优雅,这里提供一个Python使用哨兵节点将头结点变成普通节点的方案哈~
解题思路:
循环查找是否相等,当满足删除条件(链表当前节点=val)时,执行链表删除操作,注意边界条件和特殊情况的处理。
方法1:
function deleteNode( head , val ) { // write code here // 先处理特殊情况,即头结点就是所需要删除的值,则直接将头结点赋值为next // 为什么要特殊处理这个情况?因为带入到普通处理的while循环中,执行情况为: // 第一次带入,则不满足条件,不会执行while循环,接入向下执行pre.next=cur.next, // 执行结果即为,null的next节点为第二个节点,不符合单链表规则 // 代码书写中,一定要注意特殊情况和边界条件 if(head.val===val) return head=head.next //设置一个pre前节点,以便删除操作 var pre=null var cur=head while(cur.next){ // 比较相同,删除节点 if(cur.val==val){ // 将前一个节点的next直接连接到下一个节点,达到了删除cur节点的效果 pre.next=cur.next // break跳出循环 break; } // 一定要注意赋值顺序!!! pre=cur cur=cur.next; } return head; } module.exports = { deleteNode : deleteNode };
方法2:
function deleteNode( head , val ) { // write code here // 先处理特殊情况,即头结点就是所需要删除的值,则直接将头结点赋值为next // 为什么要特殊处理这个情况?因为带入到普通处理的while循环中,执行情况为: // 第一次带入,则不满足条件,不会执行while循环,接入向下执行pre.next=cur.next, // 执行结果即为,null的next节点为第二个节点,不符合单链表规则 // 代码书写中,一定要注意特殊情况和边界条件的处理 if(head.val===val) return head=head.next //设置一个pre前节点,以便删除操作 var pre=null var cur=head // 链表当前值 与val值不相等时,一直向下找 while(cur.val!=val){ pre=cur; cur=cur.next; } // 跳出循环向下执行,说明,链表当前值与val相等,执行链表删除操作 pre.next=cur.next; return head; } module.exports = { deleteNode : deleteNode };
两种方法的区别在于,while循环找出相同节点的部分代码。
public ListNode deleteNode (ListNode head, int val) { // write code here if(head.val != val){ head.next = deleteNode(head.next, val); } if(head.val == val){ head = head.next; } return head; }
public ListNode deleteNode (ListNode head, int val) { if (head.val == val) { head = head.next; return head; } ListNode cur = head; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; break; } cur = cur.next; } return head; }
struct ListNode* deleteNode(struct ListNode* head, int val ) { //val在头结点的情况,直接更新头结点指针 if(head->val == val) { head = head->next; return head; } //val不在头结点的情况,定位val结点位置 struct ListNode* pcur = head;//val结点 struct ListNode* prev = head;//val结点的前驱指针 while(pcur->val != val) { prev = pcur; pcur = pcur->next; } prev->next = pcur->next; return head; }