数据结构与算法之美
王争
前Google工程师
立即订阅
71610 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

春节7天练 | Day 1:数组和链表

王争 2019-02-04
你好,我是王争。首先祝你新年快乐!
专栏的正文部分已经结束,相信这半年的时间,你学到了很多,究竟学习成果怎样呢?
我整理了数据结构和算法中必知必会的 30 个代码实现,从今天开始,分 7 天发布出来,供你复习巩固所用。你可以每天花一点时间,来完成测验。测验完成后,你可以根据结果,回到相应章节,有针对性地进行复习。
除此之外,@Smallfly 同学还整理了一份配套的 LeetCode 练习题,你也可以一起练习一下。在此,我谨代表我本人对 @Smallfly 表示感谢!
另外,我还为假期坚持学习的同学准备了丰厚的春节加油礼包
2 月 5 日 -2 月 14 日,只要在专栏文章下的留言区写下你的答案,参与答题,并且留言被精选,即可获得极客时间 10 元无门槛优惠券。
7 篇中的所有题目,只要回答正确 3 道及以上,即可获得极客时间 99 元专栏通用阅码。
如果 7 天连续参与答题,并且每天的留言均被精选,还可额外获得极客时间价值 365 元的每日一课年度会员。

关于数组和链表的几个必知必会的代码实现

数组

实现一个支持动态扩容的数组
实现一个大小固定的有序数组,支持动态增删改操作
实现两个有序数组合并为一个有序数组

链表

实现单链表、循环链表、双向链表,支持增删操作
实现单链表反转
实现两个有序的链表合并为一个有序链表
实现求链表的中间结点
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(98)

  • 李皮皮皮皮皮
    感谢分享,虽然工作很忙,每天下班就不想动了。但是还是要不断克服自己。数据结构和算法的重要性可能在面试的时候才能深刻感悟。如果平时多下点功夫,结果可能会大不一样。前面很多期因为各种原因没有跟上,庆幸的是后面慢慢追上了。现在养成每天做一道算法题的习惯。每天装着一道算法题在脑子里。这感觉其实也不错,不是任务,感觉像是习惯😄
    2019-02-04
    38
  • Jerry银银
    早上起来拿出电脑,准备做题。
    老妈说:今天就别工作了,玩一天吧,啥也别干,啥也别想。
    我说:不行呀,老师布置了题目,必须得做呀。
    老妈说:大过年的老师还在工作,真不容易,替我向你老师说声:🔥🔥新年好!!!
    2019-02-05
    34
  • Smallfly
    哈哈,被提名了,谢谢老师。

    有兴趣的同学可以把你的答案分享到 Github: https://github.com/iostalks/Algorithms

    有问题也可以在 issue 中一起讨论。

    新的一年跟大家一起进步,一起流弊。
    2019-02-05
    2
    26
  • fancyyou
    新年好!
    leetcode的题都做过了😁。
    2019-02-05
    15
  • abner
    Java语言实现一个大小固定的有序数组,支持动态增删改操作
    代码如下:
    public class Array {
        private String[] data;
        private int count;
        privvate int size;
        public Array(int capacity) {
            data = new String[capacity];
            count = 0;
            size = capacity;
        }
        public boolean insert(int index, String value) {
            if (count >= size) {
                return false;
            }
            if (index < 0 || index > count) {
                return false;
            }
            for (int i = count - 1;i >= index;i--) {
                 data[i+1] = data[i];
            }
            data[index] = value;
            count++;
        }
        public String delete(int index, String value) {
            if (count == 0) {
                return false;
            }
            if (index < 0 || index >count) {
                 return false;
             }
            value = data[index];
            for (int i = index;i <= count - 1;i++) {
                data[i - 1] = data[i];
            }
            count--;
            return value;
    }
    2019-02-05
    3
    4
  • _CountingStars
    合并有序数组 go 语言实现
    package main

    import "fmt"

    func mergeOrderedArray(a, b []int) (c []int) {
    i, j, k := 0, 0, 0
    mergedOrderedArrayLength := len(a) + len(b)
    c = make([]int, mergedOrderedArrayLength)
    for {
    if i >= len(a) || j >= len(b) {
    break
    }

    if a[i] <= b[j] {
    c[k] = a[i]
    i++
    } else {
    c[k] = b[j]
    j++
    }
    k++
    }

    for ; i < len(a); i++ {
    c[k] = a[i]
    k++
    }

    for ; j < len(b); j++ {
    c[k] = a[j]
    k++
    }

    return
    }

    func main() {
    a := []int{1, 3, 5, 7, 9, 10, 11, 13, 15}
    b := []int{2, 4, 6, 8}
    fmt.Println("ordered array a: ", a)
    fmt.Println("ordered array b: ", b)
    fmt.Println("merged ordered array: ", mergeOrderedArray(a, b))
    }
    2019-02-05
    4
  • 第三题,看这题,我就会想到用快排的思想在一堆数中求第n大。于是乎我就套,先把负数全部移掉,o(n)不影响。然后每轮迭代随机取个数n,比它小的放左边,比他大的放右边。比如说第一轮迭代,左边的数据个数小于n-1那么必然在左边。但这里有个问题是数据是可以重复的,怎么办,想呀想,我就选定n后,开始扫描,如果是1我就放第一个位置,如果是2我就放第二个位置,如果再有1,发现重复了,不用移动了,这样我就能计算小于n大于n的正整数有多少种了,然后就能迭代下去了。当然里面还有些细节,比如如果n很大已超过了数组长度,那说明那个数一定在左边。

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-05
    4
  • abner
    java实现一个动态扩容的数组(扩容2倍)
    代码如下:
    package array;

    public class DynamicArray {
        
        private String[] data;
        private int count;
        private int size;
        
        public DynamicArray(int capacity) {
            data = new String[capacity];
            count = 0;
            size = capacity;
        }
        
        public String[] expand(String[] data) {
            if (count >= size) {
                String[] newArray = new String[this.size * 2];
                this.size = this.size * 2;
                for (int i = 0;i < count;i++) {
                    newArray[i] = this.data[i];
                }
                return newArray;
            } else {
                return this.data;
            }
        }
        
        public boolean append(String item) {
            if (count >= size) {
                this.data = expand(this.data);
            }
            this.data[count] = item;
            count++;
            return true;
        }
        
        public void printAll() {
            for (int i = 0;i < count;i++) {
                System.out.print(data[i] + " ");
            }
            System.out.println();
        }
        
        public static void main(String[] args) {
            DynamicArray dynamicArray = new DynamicArray(5);
            for (int i = 0;i < dynamicArray.size;i++) {
                dynamicArray.data[i] = "This value is " + i;
                dynamicArray.count++;
            }
            dynamicArray.append("This value is 5");
            System.out.println("Now the size of data is " + dynamicArray.size);
            dynamicArray.printAll();
        }
      
    }
    2019-02-13
    3
  • 未来的胡先森
    求众数
    解题思路:将数组排序,统计每个数字出现的次数,当满足众数条件时返回。时间复杂度 nlogn

    int compare(const void *a, const void *b)
    {
    return (*(int*)a - *(int*)b);
    }
    int majorityElement(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int), compare);
    int num = nums[0],flag=numsSize>>1,count=1;
    for (int i = 1; i < numsSize; i++)
    {
    if (nums[i] != num)
    {
    num = nums[i]; count = 1;
    }
    else
    {
    count++;
    }
    if (count > flag)
    break;
    }
    return num;
    }
    更优解

    数组元素为奇数个,众数数量大于半数,所以相互抵消后最后剩余的一定为众数,时间复杂度 O(n)

    int majorityElement(int* nums, int numsSize)
    {
    int count = 1,num=nums[0];
    for (int i = 1; i < numsSize; i++)
    if (count == 0 || num == nums[i])
    {
    count++; num = nums[i];
    }
    else
    count--;
    return num;
    }
    2019-02-16
    2
  • kai
    3. 实现求链表的中间结点
    public class FindMidNode {

        // 1. T(n) = O(2*n) 遍历2次
        public static Node findMidNode(Node head) {
            if (head == null) {
                return null;
            }

            int len = 0;
            Node p = head;

            while(p != null) {
                len++;
                p = p.next;
            }

            p = head;
            for (int i = 0; i < len/2; i++) {
                p = p.next;
            }

            return p;
        }

        // 2. T(n) = O(n) 遍历1次
        // 快慢指针法
        public static Node findMidNodeFast(Node head) {
            if (head == null) {
                return null;
            }

            Node fast = head;
            Node slow = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            return slow;
        }


        public static Node createNode(int value) {
            return new Node(value, null);
        }

        public static class Node {
            public int data;
            public Node next;

            public Node(int data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
    }

    4. Linked List Cycle I(环形链表)
    /**
     * 141. Linked List Cycle
     * https://leetcode.com/problems/linked-list-cycle/
     */
    public class LinkedListCycle {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) {
                return false;
            }

            ListNode fast = head;
            ListNode slow = head;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) return true;
            }

            return false;
        }

        public static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) { val = x;}
        }
    }
    2019-02-11
    2
  • kai
    1. 实现单链表反转:
    /**
     * 206. Reverse Linked List
     * https://leetcode.com/problems/reverse-linked-list/
     */
    public class ReverseList {
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) return head;

            ListNode pre = null;
            ListNode next = null;

            while (head != null) {
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }

            return pre;
        }

        public static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) {
                this.val = val;
            }
        }
    }

    2. 实现两个有序的链表合并为一个有序链表
    /**
     * 21. Merge Two Sorted Lists
     * https://leetcode.com/problems/merge-two-sorted-lists/
     */
    public class Merge2SortedLists {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;

    // 利用哨兵(前哨节点)简化实现难度
            ListNode outpost = new ListNode(-1);
            ListNode temp = outpost;

            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    temp.next = l1;
                    l1 = l1.next;
                } else {
                    temp.next = l2;
                    l2 = l2.next;
                }

                temp = temp.next;
            }

            if (l1 == null) {
                temp.next = l2;
            }

            if (l2 == null) {
                temp.next = l1;
            }

            return outpost.next;
        }

    public ListNode mergeTwoListsRecur(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    if (l1.val < l2.val) {
    l1.next = mergeTwoListsRecur(l1.next, l2);
    return l1;
    } else {
    l2.next = mergeTwoListsRecur(l1, l2.next);
    return l2;
    }
    }

        public static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) { val = x;}
        }
    }


    2019-02-11
    2
  • 纯洁的憎恶
    1.Three Sum:暴力匹配三元组,三层循环结束后打印保存三元组的数组即可,时间复杂度O(n^3),空间复杂度O(n)。简化一下,为减少比较次数先排序。外层循环i遍历数组,内层循环从数组两头元素(s、t)开始考察,找出使num【s】+num【t】=-num【i】的s和t,若大了t- -,若小了s++(内层要避开i)s大于等于t则匹配失败。这样两层循环就可以了,时间复杂度O(n^2)。

    2.Majority Element:重点在于统计每个元素出现次数,可以先排序,然后顺序计算出每个数的出现次数,与阈值比较,大于则输出,时间复杂度O(nlogn)。也可以采用散列表,把每个元素存入散列表,并记录出现次数,最后把出现次数超过阈值的元素输出即可,时间复杂度O(n),空间复杂度O(n)。

    3.Missing Positive:本来想用散列表,发现要求时间复杂度O(n),空间复杂度为常量,有点捉急。只能从原数组上做文章。假设数组A长度为n,若i为1到n的正整数,若i存在于A中,我们就把它的位置调整到A【i-1】处,这样通过A【i】是否为i+1即可知道i+1是否在数组中。那么A中不满足上述条件的最小下标+1即为缺失的最小正整数值。

    4. Linked List Cycle I(环形链表):用图的拓扑排序算法可以,但是要统计顶点出入度,空间复杂度无法达到O(1)。那可以用快慢指针,*fast以*slow的两倍速前进,如果fast和slow重合则说明有环。

    5. Merge k Sorted Lists(合并 k 个排序链表):两两硬生生合并,时间复杂度应该是O(kN),再高级的方法想不出来。ps:如果可以抛弃原来的链表,那么新建一个合并后链表的时间复杂度可以是O(N)吧?N是k个链表的总长。
    2019-02-08
    2
  • William
    特地新开了一个git仓库,https://github.com/Si3ver/LeetCode。刷完5道题,思路大致写一下。1.数组三数之和,时间复杂度是O(n^2),先排序,外层i遍历数组,内层左右双指针,寻找两数之和 = -nums[i]。 2. 求数组中出现次数大于一半的数字。复杂度O(n),是利用摩尔投票法。3.求缺失的最小正整数,复杂度O(n),思路是哈希表统计。4.环形链表用快慢指针。5.合并k个有序链表,用的是两两归并,据说用堆会更快,这个有待补充。

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-06
    2
  • 菜菜
    大小固定的有序数组,支持增删改:既然有序,则查询操作都可以用二分查询。增加操作,找到第一个大于新数据的值的位置,从最后一个有效数据往后移一个位置,目的是为了给新数据腾位置,然后插入。删除操作:找到第一个等于要删除的数据的值,然后将其后面的数据依次向前挪一个位置。改操作,查询再修改。要注意临界条件和找不到数据,以及数组满等情况。
    2019-02-06
    2
  • 赵菁垚
    王老师,请教您一个问题,想参加NOIP c++考这些算法吗?

    作者回复: 也考的

    2019-08-08
    1
  • 神盾局闹别扭
    加油礼包的福利在哪里领呢?

    编辑回复: 运营同学稍后会联系获奖同学哈

    2019-02-18
    1
  • Ben
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            通过hash结构缓存去重值及出现的次数

            将值按正负区分, 将正负列表中的数字求和, 判断和的相反数是否仍存在于字典中
            """
            #将输入列表的值作为索引, 对应出现的次数作为新的字典结构的值
            dic = {}
            for ele in nums:
                if ele not in dic:
                    dic[ele] = 0
                dic[ele] += 1
            # 存在3个0的特殊情况
            if 0 in dic and dic[0] > 2:
                rst = [[0, 0, 0]]
            else:
                rst = []

            pos = [p for p in dic if p > 0]
            neg = [n for n in dic if n < 0]

            # 若全为正或负值, 不存在和为0的情况
            for p in pos:
                for n in neg:
                    inverse = -(p + n)
                    if inverse in dic:
                        if inverse == p and dic[p] > 1:
                            rst.append([n, p, p])
                        elif inverse == n and dic[n] > 1:
                            rst.append([n, n, p])
                        # 去重: 小于负值且大于正值可以排除掉重复使用二者之间的值
                        elif inverse < n or inverse > p or inverse == 0:
                            rst.append([n, inverse, p])
            return rst
        def majorityElement(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            hash反存值和出现的次数
            """
            #利用字典表反存值:出现的次数
            dic = {}
            for i in nums:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] +=1
            
            #根据列表获取值最大的索引
            vs = list(dic.values())
            return list(dic.keys())[vs.index(max(vs))]
        def firstMissingPositiveFast(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = 1
            while n in nums:
                n +=1
            return n

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您10元无门槛优惠券,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-14
    1
  • hopeful
    //单链表反转(带头结点)
    void reverse(struct node* head){
    struct node* L;
    struct node* p;
    struct node* p2;
    struct node* p3;
    L = head->next;
    if(head == NULL){
    printf("链表未创建");
    }else if(L->next==NULL){
    printf("单链表只有一个节点,无需反转");
    return;
    }else if(L->next->next == NULL){
    head->next = L->next;
    head->next->next = L;
    L->next = NULL;
    printf("单链表反转成功");
    }else{
    p = L;
    p2 = L->next;
    p3 = L->next->next;
    while(p3!=NULL){
    p2->next = p;
    p = p2;
    p2 = p3;
    p3 = p3->next;
    }
    p2->next = p;
    L->next = NULL;
    head->next = p2;
    printf("单链表反转成功");
    }
    }
    2019-02-13
    1
  • 恋恋
    Three Sum(求三数之和)Go语言:
    func threeSum(nums []int) [][]int {
        results := [][]int{}
    n := len(nums)
    if n == 0 || n < 3 {
    return results
    }
    sort.Ints(nums) //首先,对数组进行排序
    for i := 0; i < n-2; i++ {
    if i > 0 && nums[i] == nums[i-1] { //如果相邻两个数相等
    continue
    }
    target := -nums[i]
    left := i + 1
    right := n - 1
    for left < right {
    sum := nums[left] + nums[right]
    if sum == target {
    results = append(results, []int{nums[left], nums[right], nums[i]})
    left++
    right--
    for left < right && nums[left] == nums[left-1] {
    left++
    }
    for left < right && nums[right] == nums[right+1] {
    right--
    }
    } else if sum > target {
    right--
    } else if sum < target {
    left++
    }
    }

    }
    return results
    }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-12
    1
  • Sharry
    链表篇
    1. 翻转单链表
    /*翻转单链表*/
    void reversalList(Node<int>* head) {
    Node<int>* p = head;
    Node<int>* prev = NULL;
    Node<int>* temp = NULL;
    while (p) {
    // 1. 保存要遍历的下一个结点
    temp = p->next;
    // 2. 将 node->next 指向前驱结点
    p->next = prev;
    // 3. 更新前驱结点
    prev = p;
    // 4. 更新下一个要遍历的结点
    p = temp;
    }
    }

    2. 将两个有序的单链表合并
    /* 合并两个有序链表, 将 list2 合并到 list1 中 */
    Node<int>* mergeOrderList(Node<int>* list1, Node<int>* list2) {
    // 记录 list2 的头结点
    Node<int>* head = list2;
    // 创建哨兵, 用于处理将 list2 中的元素插入到 list1 头结点前面的情况
    Node<int>* sentry = new Node<int>(-1);
    sentry->next = list1;
    // 记录 list1 要遍历的元素
    Node<int>* node = sentry;
    Node<int>* temp = NULL;
    while (node->next && head) {
    if (node->next->data > head->data) {
    temp = head->next;
    head->next = node->next;
    node->next = head;
    head = temp;
    }
    else {
    node = node->next;
    }
    }
    // 若 list2 的头结点不为 NULL, 则说明 list1 中的元素提前遍历结束了
    // 剩下的 list2 中的元素均比 list1 中的大
    // 直接将 list1 的尾结点连接到 list2 的首结点即可
    if (head) {
    node->next = head;
    }
    // 释放哨兵结点内存
    list1 = sentry->next;
    sentry->next = NULL;
    delete(sentry);
    return list1;
    }

    3. 求单链表的中间结点
    /* 查询单链表的中间结点 */
    template<typename E>
    Node<E>* findMidNode(Node<E>* head, Node<E>** mid_node) {
    if (!head) {
    return NULL;
    }
    Node<E>* fast = head;
    Node<E>* slow = head;
    while (fast && fast->next && fast->next->next) {
    // 快指针走两步
    fast = fast->next->next;
    // 慢指针走一步
    slow = slow->next;
    }
    *mid_node = slow;
    }

    编辑回复: 感谢您参与春节七天练的活动,为了表彰你在活动中的优秀表现,赠送您99元专栏通用阅码,我们会在3个工作日之内完成礼品发放,如有问题请咨询小明同学,微信geektime002。

    2019-02-12
    1
收起评论
98
返回
顶部