给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。
返回删除后的链表的头节点。
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
来源:力扣(LeetCode)
思路:
首先找到值等于val的节点,即head->val == val;
设当前节点为cur,其前驱节点为pre,若删除cur节点,则pre->next = cur->next;
特殊,如果头节点等于val;直接返回head->next.
初始化,pre=head,cur = head->next
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 != nullptr && cur->val != val) { pre = cur; cur = cur->next; } if( cur != nullptr) pre->next = cur->next; return head; } };
复杂度分析:
时间复杂度 O(N): N为链表长度,删除 *** 作平均需循环 N/2 次,最差为N 次。
空间复杂度 O(1): cur, pre 占用常数大小额外空间。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)