精华内容
下载资源
问答
  • static Node sortList(Node head) { if (head == null || head.next == null) { return head; } Node mid = findMiddle(head); Node right = mid.next; mid.next = null;... Node pre = sortList(head);...
    static Node sortList(Node head) {
            if (head == null || head.next == null) {
                return head;
            }
            Node mid = findMiddle(head);
            Node right = mid.next;
            mid.next = null;
            Node pre = sortList(head);
            Node pos = sortList(right);
            return merge(pre, pos);
        }
        
    static Node findMiddle(Node head) {
            Node slow = head;
            Node fast = head.next;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
    private static Node merge(Node left, Node right) {
            Node head = new Node();
            Node tmp = head;
            while (left != null && right != null) {
                if (left.val <= right.val){
                    tmp.next = left;
                    left = left.next;
                }else {
                    tmp.next = right;
                    right = right.next;
                }
                tmp = tmp.next;
            }
            while (left!= null){
                tmp.next = left;
                tmp = tmp.next;
                left = left.next;
            }
            while (right!=null){
                tmp.next = right;
                tmp = tmp.next;
                right = right.next;
            }
            return head.next;
        }
    
    展开全文
  • 单向链表的时间复杂度 在单向链表原理和实现中已经和动态数组相比对比并分析了单向链表的时间复杂度: 情况分类 添加 删除 最好 头节点 O(1) O(1) 最差 尾节点 O(n) O(n) 平均 O(n) O(n) 双向链表的...

    单向链表的时间复杂度

    单向链表原理和实现中已经和动态数组相比对比并分析了单向链表的时间复杂度:

    情况分类添加删除
    最好 头节点O(1)O(1)
    最差 尾节点O(n)O(n)
    平均O(n)O(n)

    双向链表的时间复杂度

    查找节点

    因为对节点的添加和删除操作需要查找对于index的节点,首先分析以下查找节点的代码:

    - (JKRLinkedListNode *)nodeWithIndex:(NSInteger)index {
        [self rangeCheckForExceptAdd:index];
        // _size >> 1 相当于 floor(_size / 2),位运算可以大大节省计算时间
        if (index < (_size >> 1)) { // 当index位于链表的前半,从头节点向后查找
            JKRLinkedListNode *node = _first;
            for (NSUInteger i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { // 当index位于链表的后半,从尾节点向前查找
            JKRLinkedListNode *node = _last;
            for (NSUInteger i = _size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    复制代码

    当index == 0 或 index == _size - 1时,即查找头节点和尾节点时,直接就可以一次查找就拿到需要的节点。越靠近头节点或尾节点,查找需要遍历的次数越小,最坏的情况就是查找中间的节点,需要 n / 2 次查找。

    添加和删除

    - (void)insertObject:(id)anObject atIndex:(NSUInteger)index {
        [self rangeCheckForAdd:index];
        
        if (index == _size) { // index == size 相当于 插入到表尾 或者 空链表添加第一个节点
            JKRLinkedListNode *oldLast = _last;
            JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:_last object:anObject next:nil];
            _last = node;
            // 还可以用 !oldLast 、 !_first 判断
            if (_size == 0) { // 空链表添加第一个节点
                _first = _last;
            } else { // 添加到表尾
                oldLast.next = _last;
            }
        } else { // 插入到表的非空节点的位置上
            JKRLinkedListNode *next = [self nodeWithIndex:index];
            JKRLinkedListNode *prev = next.prev;
            JKRLinkedListNode *node = [[JKRLinkedListNode alloc] initWithPrev:prev object:anObject next:next];
            next.prev = node;
            // 还可以用 !prev 、 next == _first 判断
            if (index == 0) { // 插入到表头
                _first = node;
            } else { // 插入到表中间
                prev.next = node;
            }
        }
        _size++;
    }
    复制代码

    由于添加的所有情况对节点prev和next操作都是相同的,区别就是通过index查找节点,这取决于上面查找节点的复杂度。因此可以推出结论,双向链表删除头节点、尾节点都是O(1),越靠近头节点或尾节点操作时间越快,越靠近链表中间越慢。平均复杂度为O(n),而删除同添加。

    双向链表时间复杂度

    情况分类添加删除
    最好 头节点O(1)O(1)
    最好 尾节点O(1)O(1)
    平均O(n)O(n)

    单向链表和双向链表时间复杂度对比

    由上面的结论可以知道,单向链表和双向链表在操作头节点、链表的前半部分、链表的中间节点时都是一样的。而双向链表在操作尾节点、链表后半部分是大大优于单向链表的。

    下面是一段对比测试,分别对比了单向链表和双向链表在对头节点、尾节点、前半部分节点、后半部分节点、中间节点这五种情况下的对比:

    void compareSingleLinkedListAndLinkedList() {
        NSUInteger testCount = 50000;
        
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRSingleLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:0];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeFirstObject];
            }
            NSLog(@"单向链表操作头节点");
        }];
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:0];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeFirstObject];
            }
            NSLog(@"双向链表操作头节点");
        }];
        
        
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRSingleLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array addObject:[NSNumber numberWithInteger:i]];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeLastObject];
            }
            NSLog(@"单向链表操作尾节点");
        }];
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array addObject:[NSNumber numberWithInteger:i]];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeLastObject];
            }
            NSLog(@"双向链表操作尾节点");
        }];
        
        
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRSingleLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 2];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count >> 2];
            }
            NSLog(@"单向链表操作 index = 总节点数*0.25 节点");
        }];
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 2];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count >> 2];
            }
            NSLog(@"双向链表操作 index = 总节点数*0.25 节点");
        }];
        
        
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRSingleLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count * 0.75];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count * 0.75];
            }
            NSLog(@"单向链表操作 index = 总节点数*0.75 节点");
        }];
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count * 0.75];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count * 0.75];
            }
            NSLog(@"双向链表操作 index = 总节点数*0.75 节点");
        }];
        
        
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRSingleLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 1];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count >> 1];
            }
            NSLog(@"单向链表操作中间节点");
        }];
        [JKRTimeTool teskCodeWithBlock:^{
            JKRBaseList *array = [JKRLinkedList new];
            for (NSUInteger i = 0; i < testCount; i++) {
                [array insertObject:[NSNumber numberWithInteger:i] atIndex:array.count >> 1];
            }
            for (NSUInteger i = 0; i < testCount; i++) {
                [array removeObjectAtIndex:array.count >> 1];
            }
            NSLog(@"双向链表操作中间节点");
        }];
    }
    复制代码

    打印结果:

    单向链表操作头节点
    耗时: 0.020 s
    双向链表操作头节点
    耗时: 0.038 s
    
    单向链表操作尾节点
    耗时: 49.085 s
    双向链表操作尾节点
    耗时: 0.033 s
    
    单向链表操作 index = 总节点数*0.25 节点
    耗时: 12.144 s
    双向链表操作 ndex = 总节点数*0.25 节点
    耗时: 12.215 s
    
    单向链表操作 index = 总节点数*0.75 节点
    耗时: 35.735 s
    双向链表操作 index = 总节点数*0.75 节点
    耗时: 18.488 s
    
    单向链表操作中间节点
    耗时: 23.856 s
    双向链表操作中间节点
    耗时: 36.420 s
    复制代码

    上面的打印可以看到,单向链表在操作头节点、尾节点、中间节点、前半部分节点时,部分情况是优于双向链表,这也是由于单向链表对节点操作次数少于双向链表,因为它不用操作节点指向前一个节点的指针。但是当操作后半部分节点、尾节点时,单向链表的效率就会大大低于双向链表。

    所以,当只需要对数据的头部或者前半部分进行操作时,单向链表和双向链表时间复杂度一致,并且单向链表更加精简高效。但是如果需要对数据的头部、尾部都要进行操作时,双向链表大大优于单向链表。

    展开全文
  • 双向链表为何时间复杂度为O(1)?

    千次阅读 2019-09-25 05:59:57
    若仅仅知道待删除节点,是不能知道前驱节点的,故单链表的增删操作复杂度为O(n)。 双链表(双向链表)知道要删除某一节点p时,获取其前驱节点q的方式为 q = p->prior,不必再进行遍历。故...

            双向链表相比于单向链表,所谓的O(1)是指删除、插入操作。

           单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(通过待删除节点序号或按值查找)。若仅仅知道待删除节点,是不能知道前驱节点的,故单链表的增删操作复杂度为O(n)。 双链表(双向链表)知道要删除某一节点p时,获取其前驱节点q的方式为 q = p->prior,不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号,则依然要按序查找,时间复杂度仍为O(n)。

           单、双链表的插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(n)。至于查找,二者的时间复杂度均为O(n)。 对于最基本的CRUD操作,双链表优势在于删除给定节点。但其劣势在于浪费存储空间(若从工程角度考量,则其维护性和可读性都更低)。

           双链表本身的结构优势在于,可以O(1)地找到前驱节点,若算法需要对待操作节点的前驱节点做处理,则双链表相比单链表有更加便捷的优势。

     

    转载于:https://www.cnblogs.com/RambleIvy/p/11414116.html

    展开全文
  • 数组的优缺点 (参考拉勾教育的300分钟搞定数据结构与算法) 优点: 1、构建简单; 2、能在O(1)时间里根据数组的下标(index)查询某个元素。...也与是单链表还是双链表有关,双链表如果已知该元素的后一
  • 反转链表,最简单的就是使用栈了,放进栈里然后拿出来,但这样的操作使用的空间复杂度是O(N)..其实可以做到空间复杂度是O(1)的。public class C08_RevolveLinked1 { // 单向链表 public static class Node { int...
  • 剑指offer— 合并两个排序的链表 题目描述 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 ...
  • 下面简单的分析一下数组和链表分别在有序和无须情况下的时间复杂度。 数组 1、有序数组的删除:数组的存储地址是连续的,我们删除数组中的某个值,首先我们要找到要删除的值,删除此值后,若此值后面还有其他值,每...
  • 时间复杂度 查询 O(1) 插入(空间充足) O(1) 插入(空间不足) O(n)+O(1)=O(n) 删除(末尾元素) O(1) 删除(非末尾元素且元素个数>1) O(1)+O(n)=O(n) 分析 1.查询:通过index直接定....
  • 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6 """ ''' 思考: 三种方法:暴力、分治、最小堆(优先队列) 暴力解法...
  • 注意看带头结点的双向链表,他的时间效率,不管哪种操作,都是O(1),实际上是利用了空间提高时间
  • 假设本帅博主有链表arr1: ...我要如何才能够合并这两个有序链表,使得合并后的链表有序,并且使算法的时间复杂度为O(n)呢? 思考一下噢~ ....... 本帅博主也就不说别的啦,直接上代码: ...
  • 数组 优点:构建简单,支持随机访问,能在O(1)的时间里根据数组下标来查询... 对于最基本的CRUD操作,双链表优势在于删除给定节点的时间复杂度仅为O(1),但它的劣势在于浪费了存储空间,而且维护性和可读性也比较低。
  • 为此,我觉得有必要专门开几篇文章写写链表相关的内容,但是如果从零开始写起太过于枯燥,文章也会变得冗长,所以本文只写一些总结性的内容,对其中的原理不深究。 另外,本文默认使用节点Node的C++定义为: ...
  • 链表实现插入排序 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ##################################用来练习插入排序...
  • 将头结点断开,把后面的节点依次取出,插入到头部,可实现O(n)复杂度链表反转效果。 演示代码 #include&amp;lt;iostream&amp;gt; #include&amp;lt;stdlib.h&amp;gt; using namespace...
  • 链表,二叉树,堆,栈等的存,取数据的时间复杂度一、常用数据结构增删查时间复杂度1、数组1.1 正常数组:1.2 无下标数组:1.3 有序无下标数组:2、链表2.1 单向无序链表:2.2 单向有序链表:2.3 二叉排序树: 一、常用...
  • 排序复杂度分析

    2021-09-12 16:21:28
    快速排序在数组很长时,是最快的一种排序算法,因为其数组元素遍历时是挨着访问的,而且其交换次数很少,所以综合效率高,堆排序也是很快的排序算法,而且堆排序的时间复杂度为nlon n,快速排序最好时间复杂度为nlon...
  • 升序链表合并为降序链表复杂度问题分析

    千次阅读 多人点赞 2019-07-27 10:04:37
    题目: ... 来源:nowcoder一位大连理工的老师的评论 解析: 这道题答案个人觉得应该为D。虽然确实比较次数最多是m+n次。...1.贡献时间复杂度的不是“移动”次数,而是“比较”,如果从“移动”的角度上考虑...
  • 数组、链表、跳表的时间复杂度和空间复杂度分析一、数组二、链表三、跳表 一、数组 1.1头插入、尾插入、中间某个位置插入 1.2 头删除、尾删除、中间某个位置删除 1.3查找 二、链表 2.1头插入、尾插入、中间某个位置...
  • 转载于:https://www.cnblogs.com/wmxl/p/11309352.html
  • 链表实现与时间复杂度分析

    万次阅读 2018-12-05 12:58:03
    一、链表:&amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp; 二、链表的两种实现: 1.不适用虚拟头节点 &amp;nbsp;  不用虚拟头节点在添加元素的操作上要单独考虑在链表的头添加...
  • 题目要求是将k个有序链表合并为一个链表,时间复杂度限定为O(nlogk)。下面给出应用最小堆方法的两个程序,最后再贴上利用分治递归法的代码,虽然时间复杂度不及堆方法,但思路相对简单好理解。 (1)最小堆方法1 用...
  • 03 | 复杂度分析(上) 1. 复杂度O(n)表示的是单位代码执行时间T(n) 随数据规模n增长的变化趋势 2.分时间复杂度和空间复杂度(表示存储空间大小) 3.常见的复杂度并不多,从低阶到高阶有:O(1)、O(n)、O(nlogn)、O...
  • 顺序表与链表时间复杂度比较

    千次阅读 2020-02-15 20:03:25
    顺序表与链表时间复杂度比较 名称 访问 查找 插入 删除 数组 O(1) O(n) O(n) O(n) 有序数组 O(1) O(logN) O(n) O(n) 链表 O(n) O(n) O(1) O(1) 有序链表 O(n) O(n) O(n) O(n) 1、向一个有序数组中...
  • 总体完成一次操作,大家都是o(n)的复杂度,为什么教材和网路上都说,要频繁删除插入操作时,选链表? 答案: 因为这个O(n)内涵不同,分别是写O(n)和读O(n)。数组擅长读取,链表擅长写入。写入要先读取定位,再写入。...
  • 下面就我自己的感受说说我对内存空间换取降低操作数据时的时间复杂度的一点浅见。 首先单向链表的结构可以简单的表示为: 头结点是节点1的引用,而节点1的next属性又是节点2的应用,以此类推,最后一个节点的next...
  • 该题是leetcode的困难题,方案一是和21题一样,先合并两个链表,合并后的链表再和下个链表继续合并,循环下去,这种方案的时间复杂度为O(k^2*n),k表示链表的个数,n表示每个链表的平均节点数。方案一在leetcode上...
  • 用C语言O(1)空间复杂度实现单链表反转,C语言数据结构的作业,有需要的尽管拿去用吧,赚点小分,无聊腻了
  • 【2013年统考真题】已知两个长度分别为m和n的升序链表,若将它们合并为长度为m+n的一个降序链表,则最坏情况下的时间复杂度是() A. O(n) B. O(mn) C. O(min(m,n)) D. O(max(m,n)) 答案是D 注意,此题中的时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 149,996
精华内容 59,998
关键字:

链表复杂度