wns9778.com_威尼斯wns.9778官网

热门关键词: wns9778.com,威尼斯wns.9778官网
wns9778.com > 计算机教程 > 搞懂单链表常见面试题

原标题:搞懂单链表常见面试题

浏览次数:126 时间:2019-05-11

我们在上篇文章里面提到了链表的翻转,给定一个链表,对每两个相邻的节点作交换,并返回头节点,今天的这道题是它的升级版,如下:

Hello 继上次的 搞懂基本排序算法,这个一星期,我总结了,我所学习和思考的单链表基础知识和常见面试题,这些题有的来自 《剑指 offer》 ,有的来自《程序员代码面试指南》,有的来自 leetCode,不是很全面,但都具有一定代表性,相信大家看完以后一定跟我一样,对面试的时候算法题又多了一份自信。

k个一组翻转链表

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针,简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里,它们可以不是连续的因为他们每个节点保存着下一个节点的引用,所以较之数组来说这是一个优势。

给出一个链表,每 个节点一组进行翻转,并返回翻转后的链表。

对于单链表的一个节点我们经常使用下边这种代码表示:

是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 的整数倍,那么将最后剩余节点保持原有顺序。

public class Node{ //节点的值 int value; //指向下一个节点的指针(java 中表现为下一个节点的引用) Node next; public void Node(int value){ this.value = value; }}

示例 :

单链表的特点

给定这个链表:1->2->3->4->5

  1. 链表增删元素的时间复杂度为O,查找一个元素的时间复杂度为 O;
  2. 单链表不用像数组那样预先分配存储空间的大小,避免了空间浪费
  3. 单链表不能进行回溯操作,如:只知道链表的头节点的时候无法快读快速链表的倒数第几个节点的值。

当 = 2 时,应当返回: 2->1->4->3->5

上一节我们说了什么是单链表,那么我们都知道一个数组它具有增删改查的基本操作,那么我们单链表作为一种常见的数据结构类型也是具有这些操作的那么我们就来看下对于单链表有哪些基本操作:

当 = 3 时,应当返回: 3->2->1->4->5

获取单链表的长度

由于单链表的存储地址不是连续的,链表并不具有直接获取链表长度的功能,对于一个链表的长度我们只能一次去遍历链表的节点,直到找到某个节点的下一个节点为空的时候得到链表的总长度,注意这里的出发点并不是一个空链表然后依次添加节点后,然后去读取已经记录的节点个数,而是已知一个链表的头结点然后去获取这个链表的长度:

public int getLength(Node head){ if(head == null){ return 0; } int len = 0; while(head != null){ len  ; head = head.next; } return len; }

说明 :

查询指定索引的节点值或指定值得节点值的索引

由于链表是一种非连续性的存储结构,节点的内存地址不是连续的,也就是说链表不能像数组那样可以通过索引值获取索引位置的元素。所以链表的查询的时间复杂度要是O级别的,这点和数组查询指定值得元素位置是相同的,因为你要查找的东西在内存中的存储地址都是不一定的。

 /** 获取指定角标的节点值 */ public int getValueOfIndex(Node head, int index) throws Exception { if (index < 0 || index >= getLength { throw new Exception; } if (head == null) { throw new Exception("当前链表为空!"); } Node dummyHead = head; while (dummyHead.next != null && index > 0) { dummyHead = dummyHead.next; index--; } return dummyHead.value; } /** 获取节点值等于 value 的第一个元素角标 */ public int getNodeIndex(Node head, int value) { int index = -1; Node dummyHead = head; while (dummyHead != null) { index  ; if (dummyHead.value == value) { return index; } dummyHead = dummyHead.next; } return -1; }
  • 你的算法只能使用常数的额外空间。

  • 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

链表添加一个元素

学过数据结构的朋友一定知道链表的插入操作,分为头插法,尾插法,随机节点插入法,当然数据结构讲得时候也是针对一个已经构造好的(保存了链表头部节点和尾部节点引用)的情况下去插入一个元素,这看上去很简单,如果我们在只知道一个链表的头节点的情况下去插入一个元素,就不是那么简单了,就对于头插入法我们只需要构造一个新的节点,然后将这个节点的 next 指针指向已知链表的头节点就可以了。

1、 在已有链表头部插入一个节点

public Node addAtHead(Node head, int value){ Node newHead = new Node; newHead.next = head; return newHead;}

2、在已有链表的尾部插入一个节点:

public void addAtTail(Node head, int value){ Node node = new Node; Node dummyHead = head; //找到未节点 注意这里是当元素的下一个元素为空的时候这个节点即为未节点 while( dummyHead.next != null){ dummyHead = dummyHead.next; } dummyHead.next = node; }

3、在指定位置添加一个节点

// 注意这里 index 从 0 开始 public Node insertElement(Node head, int value, int index) throws Exception { //为了方便这里我们假设知道链表的长度 int length = getLength; if (index < 0 || index >= length) { throw new Exception; } if (index == 0) { return addAtHead(head, value); } else if (index == length - 1) { addAtTail(head, value); } else { Node pre = head; Node cur = head.next; // while (pre != null && index > 1) { pre = pre.next; cur = cur.next; index--; } //循环结束后 pre 保存的是索引的上一个节点 而 cur 保存的是索引值当前的节点 Node node = new Node; pre.next = node; node.next = cur; } return head;}

在指定位置添加一个节点,首先我们应该找到这个索引所在的节点的前一个,以及该节点,分别记录这两个节点,然后将索引所在节点的前一个节点的 next 指针指向新节点,然后将新节点的 next 指针指向插入节点即可。与其他元素并没有什么关系,所以单链表插入一个节点时间复杂度为 O,而数组插入元素就不一样了如果将一个元素插入数组的指定索引位置,那么该索引位置以后元素的索引位置都将发生变化,所以一个数组的插入一个元素的时间复杂度为 O;所以链表相对于数组插入的效率要高一些,删除同理。

 

链表删除一个元素

由于上边介绍了链表添加元素的方法这里对于链表删除节点的方法不在详细介绍直接给出代码:

1、 删除头部节点 也就是删除索引为 0 的节点:

 public Node deleteHead(Node head) throws Exception { if (head == null) { throw new Exception("当前链表为空!"); } return head.next; }

2、 删除尾节点

 public void deleteTail(Node head) throws Exception { if (head == null) { throw new Exception("当前链表为空!"); } Node dummyHead = head; while (dummyHead.next != null && dummyHead.next.next != null) { dummyHead = dummyHead.next; } dummyHead.next = null; }

3、 删除指定索引的节点:

public Node deleteElement(Node head, int index) throws Exception { int size = getLength; if (index < 0 || index >= size) { throw new Exception; } if (index == 0) { return deleteHead; } else if (index == size - 1) { deleteTail; } else { Node pre = head; while (pre.next != null && index > 1) { pre = pre.next; index--; } //循环结束后 pre 保存的是索引的上一个节点 将其指向索引的下一个元素 if (pre.next != null) { pre.next = pre.next.next; } } return head;}

由单链表的增加删除可以看出,链表的想要对指定索引进行操作,的时候必须获取该索引的前一个元素。记住这句话,对链表算法题很有用。

介绍了链表的常见操作以后,我们的目标是学习链表常见的面试题目,不然我们学他干嘛呢,哈哈~ 开个玩笑那么我们就先从简单的面试题开始:

解题思路:

寻找单链表的中间元素

同学们可能看到这道面试题笑了,咋这么简单,拿起笔来就开始写,遍历整个链表,拿到链表的长度len,再次遍历链表那么位于 len/2 位置的元素就是链表的中间元素。

咱也不能说这种方法不对,想想一下一个腾讯的面试官坐在对面问这个问题,这个回答显然连自己这一关都很难过去。那么更渐快的方法是什么呢?或者说时间复杂度更小的方法如何实现这次查找?这里引出一个很关键的概念就是 快慢指针法,这也是面试官想考察的。

假如我们设置 两个指针 slow、fast 起始都指向单链表的头节点。其中 fast 的移动速度是 slow 的2倍。当 fast 指向末尾节点的时候,slow 正好就在中间了。想想一下是不是这样假设一个链表长度为 6 , slow 每次一个节点位置, fast 每次移动两个节点位置,那么当fast = 5的时候 slow = 2wns9778.com, 正好移动到 2 的节点的位置。

所以求解链表中间元素的解题思路是:

 public Node getMid(Node head){ if(head == null){ return null; } Node slow = head; Node fast = head; // fast.next = null 表示 fast 是链表的尾节点 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }

    这道题让我们以每K个为一组来翻转链表,实际上是把原链表分成若干个小段,然后对没一个小段进行翻转。那么我们就能想到他是需要两个函数的,一个是来做分段的,一个是在对每一段做翻转的。我们就以题中给出的例子来看的话,1>2>3>4>5, k=3.一般在处理链表问题的时候,因为单向链表是不可逆的,只能从前往后遍历,所以我们一般在开头添加一个头结点,记录当前最新的头结点,值一般给为-1,那么新的链表就变为了-1>1>2>3>4>5.k=3,那么我们需要把1>2>3做翻转,做翻转的时候我们需要两个指针,pre和next分别指向要被翻转的链表的前后的位置,在这里也就是pre=-1,next=4,那么翻转完1>2>3之后变为-1>3>2>1>4>5,这个时候的pre指针应该是1。如下:

判断一个链表是否是循环链表

首先此题也是也是考察快慢指针的一个题,也是快慢指针的第二个应用。先简单说一下什么循环链表,循环链表其实就是单链表的尾部指针指向头指针,构建成一个环形的链表,叫做循环链表。 如 1 -> 2 - > 3 -> 1 -> 2 .....。为什么快慢指针再循环链表中总能相遇呢?你可以想象两个人在赛跑,A的速度快,B的速度慢,经过一定时间后,A总是会和B相遇,且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍。这也就是 Floyd判环算法

那么如何使用快慢指针去判断一个链表是否为环形链表呢:

private static boolean isLoopList(Node head){ if (head == null){ return false; } Node slow = head; Node fast = head.next; //如果不是循环链表那么一定有尾部节点 此节点 node.next = null while(slow != null && fast != null && fast.next != null){ if (fast == slow || fast.next == slow){ return true; } // fast 每次走两步 slow 每次走一步 fast =fast.next.next; slow = slow.next; } //如果不是循环链表返回 false return false; }

本文由wns9778.com发布于计算机教程,转载请注明出处:搞懂单链表常见面试题

关键词: wns9778.com

上一篇:MySql 存储引擎wns9778.com

下一篇:没有了