链表-面试高频考点解析

链表是一种基本数据结构,因为链表使用过程中指来指去的指针让大家抓狂,以至于大家面试前总是要特意看下链表相关知识。今天,我来带大家学习「链表」(Linked list) 这个数据结构。

我们总是拿链表和数组来进行比较,不同于数组需要连续内存,链表并不需要一块连续的内存,它通过「指针」将一组零散的内存块串联起来使用。

了解了链表的官方定义后,我们来看看链表有那些结构。链表包括单链表、循环链表、双向链表、双向循环链表、静态链表。我们先来看最简单、最常用的单链表。

链表通过指针将一组零散的内存块串联起来。其中,内存块称为链表的「结点」。为了将所有结点串起来,每个链表的结点除了存储数据外,还需要记录链上的下一个结点位置的指针。对于单链表,我们把记录下一个结点位置的指针叫做后继指针 next。

单链表(自己画的)

从我给你的单链表插图我们可以看出第一个结点和最后一个结点比较特殊。它们分别被称为头结点和尾节点。头结点用来记录链表的基地址,我们可以遍历得到整条链表。而尾节点的指针不是指向下一个结点,而是指向一个空地址 Null,表示这是链表上最后一个结点。

对于链表的插入和删除操作,由于只涉及前后结点指针的改变,所以对应的时间复杂度为 O(1)。但是,链表要是想要随机访问第 k 个元素就没那么简单了,和数组靠寻址公式随机访问不同。我们需要根据指针遍历得到相应结点。

其实链表相当于一个队伍,队伍里面的每一个人只知道自己的前面一个人和后面一个人,当我们去找某个人时,需要从第一个人往后数来找到某个特定的人。所以链表随机访问第 k 个元素的时间复杂度是 O(n)。

循环链表其实就是一种特殊的单链表。单链表的尾节点指向 null。循环链表的尾节点指向头结点,就像贪吃蛇吃了自己的尾巴一样,形成了一个环。所以我们管它叫循环链表。循环链表适用于解决约瑟夫问题

循环链表.png

双向链表不同于单向链表只有一个 next 指针指向后面的结点,双向链表不只有一个 next 指针指向后面的结点,还有一个前驱指针 prev 指向前面的结点。

那么单链表和双向链表到底有什么区别呢?我举链表的删除操作给你举例。

在实际的软件开发中链表的删除操作无外这非两种情况:

  • 删除结点中「值等于某个给定值」的结点;
  • 删除给定指针指向的结点。

对于第一种情况,单链表和双链表都需要从头结点开始遍历对比,直到找到等于给定值的结点,然后通过指针操作将其删除。

单纯的删除操作时间复杂度是 O(1),但遍历查找结点的时间是主要耗时点,对应的时间复杂度为 O(n)。根据时间时间度的加法原则,删除操作的时间复杂度为 O(n)。这种情况两种链表没有多大区别。

第二种情况则不一样,我们已经知道了给定的结点了,对于单链表来说,假设要删除的结点为 q, 我们还要知道 q 的前驱结点 p,我们还是要遍历链表,直到 p->q,找到 p 结点。对于双向链表情况则有所不同,我们已经有了记录前驱结点的前驱指针 prev,所以我们执行删除操作的时间复杂度为 O(1)。看出来了吧,在删除给定指针指向的结点的情况下,我们选择双向链表存储数据在 O(1) 的时间复杂度下就搞定了!而单链表需要 O(n) 的时间复杂度。

同理,对于在链表的某个特定结点 q 前插入一个新的结点,双向链表执行插入操作的时间复杂度为 O(1)。而单链表则为 O(n)。你可以自己分析一下原因。

对于有序链表,双向链表的查询效率也高于单链表。因为我们可以上次查询的结点 p, 每次查找时,我们决定往前查找还是往后查,所以平均只需要一半的数据。

学习完了链表的基础知识,下面我们进入重点,讲解面试中常考的链表相关知识。

单链表反转,合并有序链表,检测链表中是否有环。这些都是高频考点,今天我带你逐个击破。

在开始上代码前,我带你了解下写链表代码的基础知识。

我们知道指针存储了变量的内存地址,指向了这个变量,我们通过这个指针就能找到这个变量。

上面这段话可能有点拗口,没关系,我们这样理解。我们写链表时,经常会写 p->next = q。这是指 p 结点的 next 指针存储了 q 结点的内存地址,也就是 p 指向了 q。类似的还有 p->next = p->next->next。这句代码的意思是我们删除了结点 p 的后继结点(即 p 后面的那个结点)。因为我们把 p 结点的 next 指针指向了存储 p 结点的下下一个结点的内存地址。

好吧,你可能看完之后更晕了。你可以返回去多看几遍,还可以在纸上画出来。我用的是 C 语言的指针概念,没学过的同学把它理解成 Java 的引用。

在写链表代码时我们重点要留意边界条件,主要是空链表和只有一个结点的链表,我们的代码是否还能正常工作。

好了,激动人心的时刻来了,上代码吧!

单链表反转:
我用的是 Java 语言实现的,用其他语言的同学不用害怕,思路都是一样的,我会加上注释的。

public static Node reverse(Node head) {
Node previousNode = null;
Node headNode = null; // 要返回的新的头结点  
Node currentNode = head; // 头结点指向 currentNode 
while(currentNode != null) {
Node Next = currentNode.next; // 当前结点的下一个结点
// 如果下一个结点指向 null, 我们把当前结点给 headNode,返回 headNode。
if( Next == null ) { headNode = currentNode; } 
currentNode.next = previousNode;
previousNode = currentNode;
currentNode = Next;
} return headNode;           
}

单链表中检测是否有环

public boolean checkCircle(Node head) {
// 边界条件
if(head == null || head.next == null ) { return false; }
// 快慢指针,如果有环,在环内结点相遇,即 slow == fast
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null ) {
fast = fast.next.next;
slow = slow.next;
if( slow == fast) {
return true; }
}
return false;
}

有序链表合并

public static Node merge(Node p1, Node p2) {
// 还是边界条件,面试中检查边界条件特别重要,切记。
if( p1 == null) { return p2; }
if(p2 == null ) { return p1; }

// 确定头结点
Node p = p1;
Node q = p2;
Node headNode;
if(p.data < q.data ) {
headNode = p;
p = p.next;
} else {
headNode = q;
q = q.next;
}

// 结点 r 穿针引线把新的有序链表连起来。 
Node r = headNode;
while( p != null && q != null) {
if( p.data < q.data) {
r.next = p;
p = p.next; 
} else {
r.next = q; 
q = q.next;
}
// 做出一轮比较后,更新 r 结点。
r = r.next;
}
// 把剩下的结点连起来
if(q != null )
{
r.next = q; 
} else {
r.next = p; }
return headNode;
}

好了,如果你能看懂并且把我上面的三个链表操作写熟练,熟能生巧,我保证你不会再害怕手写链表了。

最后留一个思考题:在如何检测环的基础上,给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。思考一下,在评论区给我答案。

对你有帮助的话,给我个喜欢!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容