二、链表(linked-list)

这篇具有很好参考价值的文章主要介绍了二、链表(linked-list)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、定义

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

二、经典例题

(一)21.合并两个有序链表

二、链表(linked-list),Agorithm,链表,数据结构

1.思路

根据题目描述,链表l1, l2是递增的,因此容易想到使用双指针cur1和cur2遍历两链表,根据cur1.val和cur2.val的大小关系确定节点添加顺序,两节点指针交替前进,直至遍历完毕。
同时因为两个链表都是有序的,所以,当我们遍历完一个链表,剩下的那个链表如果没到结尾,可以直接跟上。

2.复杂度分析

时间复杂度 O(M+N) : M,N别为两个链表的长度,合并操作需遍历两链表。
空间复杂度 O(1): 节点引用 dum , cur使用常数大小的额外空间。

3.注意

Dummy节点的作用是作为一个虚拟的头前节点。在不知道要返回的新链表的头结点是哪一个,它可能是原链表的第一个节点,可能在原链表的中间,也可能在最后,甚至不存在(nil)。引入Dummy节点可以涵盖所有情况,并且可以使用dummy.next返回最终需要的头结点。

4.代码

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        ListNode* dummy = new ListNode(-1); // 虚拟头结点
        ListNode* cur = dummy;
        while (cur1 && cur2) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
            if (cur1 -> val > cur2 -> val) {
                cur -> next = cur2;
                cur2 = cur2 -> next;
            }
            else {
                cur -> next = cur1;
                cur1 = cur1 -> next;
            }
            cur = cur -> next; // p 指针不断前进
        }
        if (cur1) cur -> next = cur1;
        if (cur2) cur -> next = cur2;

        return dummy -> next;
    }
};

(二)86.分割链表

1.思路

具体来说,我们可以把原链表分成两个小链表,一个链表中的元素大小都小于 x,另一个链表中的元素都大于等于 x,最后再把这两条链表接到一起,就得到了题目想要的结果。

2.复杂度分析

时间复杂度 O(N): 其中 N为链表长度;遍历链表使用线性时间。

空间复杂度 O(1) : 假头节点使用常数大小的额外空间。

3.代码

/**
 * 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* partition(ListNode* head, int x) {
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        ListNode* small = dummy1;
        ListNode* big = dummy2;
        // 新建两个链表 small,big,分别用于添加所有节点值<x、节点值>=的节点
        ListNode* cur = head;
        while (cur) {
            if (cur -> val >= x) {
                big -> next = cur;
                big = big -> next;
            }
            else {
                small -> next = cur;
                small = small -> next;
            }
            cur = cur -> next;
        }
        small -> next = dummy2 -> next; // 拼接 small 和 big
        big -> next = nullptr;
        return dummy1 -> next;
    }
};

(三)23.合并 K 个升序链表

1.思路

如何快速得到 k 个节点中的最小节点,接到结果链表上?

  • 这里我们就要用到 优先级队列(二叉堆) 这种数据结构,把链表节点放入一个最小堆,就可以每次获得 k 个节点中的最小节点:

优先队列 pq 中的元素个数最多是 k,所以一次 poll 或者 add 方法的时间复杂度是 O(logk);所有的链表节点都会被加入和弹出 pq,所以算法整体的时间复杂度是 O(Nlogk),其中 k 是链表的条数,N 是这些链表的节点总数。

2.复杂度分析

时间复杂度:考虑优先队列中的元素不超过 k 个,那么插入和删除的时间代价为 O(log⁡k),这里最多有 kn 个点,对于每个点都被插入删除各一次,故总的时间代价即渐进时间复杂度为 O(kn×log⁡k)。
空间复杂度:这里用了优先队列,优先队列中的元素不超过 k个,故渐进空间复杂度为 O(k)。

3.代码

/**
 * 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:
// 时间复杂度 : O(n ∗ log(k))
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;

        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;

       priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
        [] (ListNode* a, ListNode* b) { return a->val > b->val; });

        for (auto head : lists) {
            if (head != nullptr) pq.push(head);
        }

        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            p -> next = node;
            
            if (node -> next != nullptr)
                pq.push(node->next);

            p = p -> next;
        }
    return dummy -> next;
    }
};

(四)19.删除链表中的倒数第N个节点

1.思路

假设链表有 n 个节点,倒数第 k 个节点就是正数第 n - k + 1 个节点。
是的,但是算法题一般只给你一个 ListNode 头结点代表一条单链表,你不能直接得出这条链表的长度 n,而需要先遍历一遍链表算出 n 的值,然后再遍历链表计算第 n - k + 1 个节点。
也就是说,这个解法需要遍历两次链表才能得到出倒数第 k 个节点。文章来源地址https://www.toymoban.com/news/detail-733616.html

2.复杂度分析

3.代码

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
         if (head == nullptr || n == 0) return nullptr;

        ListNode* dummy = new ListNode(-1);
        dummy -> next = head;

        ListNode* x = findFromEnd(dummy, n + 1);
        x -> next = x -> next -> next;
        return dummy -> next;
    }
    ListNode* findFromEnd(ListNode* head, int k) {

    // 代码见上文

        ListNode* slow = head;
        ListNode* fast = head;

        while (k -- && fast) {
            fast = fast -> next;
        }
        while (fast) {
            slow = slow -> next;
            fast = fast -> next;
        }
        return slow;
    }
};

到了这里,关于二、链表(linked-list)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构英文习题解析-第二章 链表List

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW2 1. For a sequentially stored linear list of leng

    2024年04月11日
    浏览(51)
  • 【数据结构】_4.List接口实现类LinkedList与链表

    目录 1.链表的结构与特点 1.1 链表的结构: 1.2 链表的特点: 2. 不带头单链表的模拟实现 3. 单链表OJ 3.1 题目1:移除链表元素:  3.2 题目2:反转一个单链表 3.3 题目3:返回链表的中间结点 3.4 题目4:链表的倒数第k个结点 3.5 题目5:合并两个有序链表 3.6 题目6:链表的回文结构

    2024年02月15日
    浏览(44)
  • 数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

    定义 一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。 线性表的类型 常见的类型:数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(44)
  • 链表 Linked List

    2024.3.15 芝士wa 参考视频:bilibli-数据结构-链表 “印度小哥讲得真好” 对于链表来说,存储数据需要两个部分,一是数据本身,二是指针,该指针指向下一个数据的地址,依次链接,直到最后一个元素,指针指向空(NULL) 遍历的时间复杂度为O(n) 插入的时间复杂度为O(n) 删除

    2024年03月17日
    浏览(40)
  • 双向链表(Double Linked List)

            虽然单向链表能够100%解决逻辑关系为“一对一”数据的存储问题,但在解决那些需要大量查找前趋节点的问题是,单向链表无疑是不能用了,因为单向链表适合“从前往后”查找,并不适合“从后往前”查找。         如果要提高链表的查找效率,那双向链表(双

    2023年04月13日
    浏览(33)
  • 数据结构-链表结构-双向链表

    双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域 前一个指针域:存储前驱节点的内存地址 后一个指针域:存储后继节点的内存地址 数据域:存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱,后指针

    2024年02月04日
    浏览(44)
  • <数据结构> 链表 - 链表的概念及结构

    概念: 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的 1、链表由一系列结点(链表中每一个元素称为结点)组成。 2、结点可以在运行时动态(malloc)生成。 3、每个结点包括两个部分:一个是存储数据元素的

    2023年04月09日
    浏览(44)
  • 【数据结构-链表-01】反转链表

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月10日
    浏览(43)
  • LeetCode 92. Reverse Linked List II【链表,头插法】中等

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(39)
  • 数据结构——线性数据结构(数组,链表,栈,队列)

    数组(Array) 是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。 我们直接可以利用元素的索引(index)可以计算出该元素对应的存储地址。 数组的特点是: 提供随机访问 并且容量有限。 2.1. 链表简介 链表(LinkedList) 虽然是

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包