【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点

简介: 【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点

力扣对应题目链接:LCR 136. 删除链表的节点 - 力扣(LeetCode)


一、《剑指 Offer》内容


二、分析题目

1、信息交换法

《剑指Offer》上给的这段代码,我把它称为信息交换法。

这道题其实考察了我们对链表的操作和时间复杂度的理解。

一般来讲,正常的解法时间复杂度都是 O(N),因为我们要找到待删除节点,不得不牺牲 O(N) 的时间复杂度。那么 O(1) 的时间复杂度是如何实现的呢?这里有一个信息交换法,即:假如 head 为 4 -> 5 -> 1 -> 9,val 为 5 -> 1 -> 9,表示我们要删除结点 5,这时我们使用信息交换,把 val 改为 1 -> 9的信息即可。为什么呢?因为我们把待删除节点的后一个元素赋值给待删除节点,也就相当于删除了当前元素。但也可以举出反例:如果 val 的值是最后一个元素 9 呢?我们无法找到 9 的后一个元素(因为没有),只能重头开始找待删除元素 9,这样的话时间复杂度再次变成了 O(N)。这就是这道题目有意思的地方,如果删除节点为前面的 n−1 个节点,时间复杂度均为 O(1),只有删除节点为最后一个的时候,时间复杂度才会变成 O(n)。平均时间复杂度为:(O(1)×(n−1)+O(n))/n=O(1),仍然为 O(1)。


【常规写法】

2、单指针

要删除链表中节点值为 val 的节点,只需要进行如下两步操作:

  1. 找到待删除节点的前一节点 cur;
  2. 将 cur->next 设置为 cur->next->next。

注意:头节点可能是待删除的节点。


3、双指针

  1. 设置两个指针分别指向头节点,pre (待删除节点的前一节点)和 cur (当前节点);
  2. 遍历整个链表,查找节点值为 val 的节点,找到了就删除该节点,否则继续查找。
  • 2.1. 找到,将当前节点的前驱节点(pre 节点或者说是之前最近一个值不等于 val 的节点)连接到当前节点(cur 节点)的下一个节点(pre->next = cur->next)。
  • 2.2. 没找到,继续遍历(cur = cur->next),更新最近一个值不等于 val 的节点(pre = cur)。

4、递归

递归的终止条件:

  1. 该节点为空节点,直接返回。
  2. 该节点就是要删除的节点,返回该节点的下一个节点。

5、设置虚拟(哨兵)头结点

之前的三种方法都需考虑头节点是否是待删除的节点,并且删除头节点的代码逻辑与删除非头节点的特别相似,可通过在头节点前面增加虚拟头节点,避免单独将拎头节点出来考虑,但是需要注意:返回的是虚拟头节点的下一节点而不是虚拟头节点。

注意:由于题目已明确是一个要删除的节点的值,因此找到该节点并删除之后,无需再遍历。


三、代码

1、参考代码

//更符合《剑指Offer》上题目的代码
class Solution {
public:
    ListNode* deleteNode(ListNode* head, ListNode* deleteNode) {
        if(head==nullptr || deleteNode==nullptr) return nullptr;
 
        // 要删除的节点不是尾节点
        if(deleteNode->next != nullptr)
        {
            ListNode* nextNode = deleteNode->next;
            deleteNode->val = nextNode->val;
            deleteNode->next = nextNode->next;
        }
        // 链表只有一个节点,删除头节点(也是尾节点)
        else if(head == deleteNode)
        {
            delete deleteNode;
            deleteNode = nullptr;
            head = nullptr;
        }
        // 链表中有多个节点,删除的节点是尾节点
        else
        {
            ListNode* p = head;
            //while(p->next != deleteNode) //另一种写法
            while(p->next != nullptr && p->next->next != nullptr)
            {
                p = p->next;
            }
            p->next = nullptr;
            delete deleteNode;
            deleteNode = nullptr;
        }
        return head;
    }
};

2、对应题目代码

//单指针
/**
 * 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->val==val) return head->next;
        ListNode* cur=head;
        while(cur->next && cur->next->val!=val)
            cur=cur->next;
        if(cur->next)
            cur->next=cur->next->next;
        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->val==val) return head->next;
        ListNode* prev=head;
        ListNode* cur=head;
        while(cur && cur->val!=val)
        {
            prev=cur;
            cur=cur->next;
        }
        if(cur)
            prev->next=cur->next;
        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==NULL) return head;
        head->next=deleteNode(head->next, val);
        if(head->val==val) return head->next;
        else 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) {
        ListNode* newHead=new ListNode(0);
        newHead->next=head;
        ListNode* cur=newHead;
        while(cur->next)
        {
            if(cur->next->val==val)
            {
                cur->next=cur->next->next;
                break;
            }
            else
            {
                cur=cur->next;
            }
        }
        return newHead->next;
    }
};

四、扩展:删除链表中重复的节点

牛客对应题目链接:删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

核心考点 :链表操作,临界条件检查,特殊情况处理。


1、《剑指Offer》(第2版) 对应内容


2、分析题目

这是一个排好序的链表,说明重复节点是连续的。

通过快慢指针的方式限定范围,进而达到去重的效果。

这里要考虑特别多的特殊情况,如:全部相同,全部不相同,部分相同等,为了方便解题我们定义头结点,主要是应对全部相同的情况。


3、代码

//牛客AC代码
 
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead==nullptr) return nullptr;
        ListNode* newHead=new ListNode(0); //考虑到链表中的元素可能全部相同,所以构造一个头结点
        newHead->next=pHead;
 
        //prev 永远在last的前面
        ListNode* prev=newHead;
        ListNode* last=prev->next;
        while(last)
        {
            // 1.如果last和last->next不相等,就一直让prev和last往后走
            while(last->next && last->val!=last->next->val)
            {
                prev=prev->next;
                last=last->next;
            }
            // 2. 如果如果last和last->next相等,就让last一直往后走
            while(last->next && last->val==last->next->val)
                last=last->next;
 
            // 走到这里结果一共有三种,注意:prev永远指向的是前驱有效节点 
            // 1. last->next != nullptr 且 (prev, last] 限定了一段重复范围
            // 2. last->next == nullptr 且 (prev, last] 限定了一段重复范围
            // 最后相当于 prev->next = nullptr
            // 3. last->next == nullptr && prev->next == last 说明从本次循环开始,
            // 整个链表中的元素都不相同,此时就不需要进行去重(特殊情况)
            if(prev->next!=last)
                prev->next=last->next;
            last=last->next;
        }
        return newHead->next;
    }
};

力扣对应题目链接:83. 删除排序链表中的重复元素 - 力扣(LeetCode)

力扣上面的这道题目和《剑指Offer》上的略微不同,它不是删除掉所有重复的元素,而是让每个元素只出现一次。

参考代码:

//力扣AC代码
/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head==nullptr) return nullptr;
        ListNode* cur=head;
        while(cur->next)
        {
            if(cur->val==cur->next->val)
                cur->next=cur->next->next;
            else
                cur=cur->next;
        }
        return head;
    }
};


相关文章
|
9天前
|
算法
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数
17 0
|
1天前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
9天前
|
算法
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数
9 0
|
9天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
18天前
题目----力扣--链表的中间结点
题目----力扣--链表的中间结点
9 0
|
19天前
查找两个链表的第一个公共结点
查找两个链表的第一个公共结点
19 0
|
20天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
20 0
|
24天前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
24天前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
24天前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈