LinkedList与链表和链表面试题

一. ArrayList 与 LinkedList 的优缺点：

ArrayList 在任意位置删除或插入元素时，就需要把后面的所有元素整体往前或者往后移动，时间复杂度为O(n)，效率较低，但是适合需要频繁访问元素的情况。空间不够会涉及到自动扩容，容易浪费空间。

LinkedList 链表可以理解为一个长长的火车，每一个 "车厢" 为一个对象元素，也叫做节点，每一个对象元素有两个或三个变量，两个变量的是单向链表，三个变量的是双向链表，其中链表其中一个变量一般是存放数据，其余的变量存放的是其他对象的引用，可以通过这个对象引用访问其他 "车厢"也就是节点。 LinkedList 适合需要频繁修改节点数据时使用。

另外，ArrayList 和 LinkedList 在内存存储上也有不同。ArrayList 它在内存中存储是连续的，而 LinkedList 存储逻辑是连续的，但是在内存不一定连续，因为 LinkedList 可以通过其节点其中的变量来找到下一个节点。

二. LinkedList 的分类

LinkedList 分为一下几种结构：

1.单向或者双向。

2.带头或者不带头。

3.循环或者非循环。

其中一一组合一共有八种结构，但是我们只需要掌握两种结构就行了：

1. 无头单向非循环链表：

这种一般在面试笔试出现会比较多。

结构如图：

val 代表的是存储的数据，next 代表存储的是下一个节点的对象引用（可以理解为下一个节点的地址），可以通过 next 找到下一个节点。

2.无头双向链表：

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

结构如图：

val 代表的是存储的数据，next 和 prev 分别代表存储的是下一个节点和上一个节点的对象引用（可以理解为下一个节点的地址），可以通过 next 找到下一个节点。也可以通过 prev 找到上一个节点。

三.链表的十道面试题：

1. 删除链表中等于给定值 val 的所有节点。题目链接

题解思路：

1.首先，要判断传过来的链表是否为空，若为空则返回 null ，否则进入下一步。

2. 其次，定义两个节点指向，一个在前，一个在后。

若后面的节点存储的值为val，则要对节点重链接，然后后节点往前走一步，前节点不动。

如果后面的节点存储的值不为val，则前节点走一步，后节点走一步。

3.最后，因为上述的过程无法判断最开始节点的值，所以再判断最开始节点的值。

题解代码：

if(head == null) {return null;}ListNode cur = head.next;ListNode curL = head;while( cur != null) {if(cur.val == val) {curL.next = cur.next;}else {curL = cur;;}cur = cur.next;}if(head.val == val) {head = head.next;}return head;

2. 反转⼀个单链表。题目链接

题解代码：

if(head == null) {return null;}if(head.next == null) {return head;}ListNode cur = head;ListNode curN = head.next;head.next = null;while(curN != null) {ListNode curNN = curN.next;curN.next = cur;cur =  curN;curN = curNN;}return cur;

题解思路：

1.首先，判断是否为空链表或者只有一个节点的链表的情况。

2.定义两个指向 cur 和 curN ，一个在前，一个在后，再把头节点置为null

3.在循环里定义个 curNN ，记录之后节点反转两个节点后 curN 所要在的地方。

注意：循环里不用 cur.next != null 作为条件，是因为cur.next当前所指向的是前一个节点，那么cur.next是访问前一个节点了。这也是什么要定义 curNN 的原因。

4.最后，返回完成后的链表的头节点。

3. 输⼊⼀个链表，输出该链表中倒数第k个结点。题目链接

题解代码：

ListNode fast = head;ListNode slow = head;int count = k-1;while(count != 0) {fast = fast.next;count--;}while(fast.next != null) {fast = fast.next;slow = slow.next;}return slow.val;

题解思路：

1.首先，定义两个指向 fast 和 slow

2.因为返回的是倒数第几个节点的值，那么可以通过让fast 先走 k-1步，再让slow 和 fast 一起走直到 fast 走到最后一个节点为止。那么slow 少走的几步就是当前的所需节点。

4.给定⼀个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。题目链接

题解代码：

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

题解思路：

1.首先，判断链表是否为空，或者只有一个节点。

2.定义一个快指针，一个慢指针。

3.每次循环让快指针走两步，慢指针走一步，当快指针遇到链表结尾，当前的慢指针就是中间节点。特别要注意循环条件。

5.将两个有序链表合并为⼀个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。题目链接

题解代码：

 if(list1 == null && list2 == null) {return null;}ListNode curA = list1;ListNode curB = list2;ListNode curN = new ListNode(1);ListNode cur = curN;while(curA != null && curB != null) {if(curA.val < curB.val) {cur.next = curA;cur = curA;curA = curA.next;}else {cur.next = curB;cur = curB;curB = curB.next;}}if(curA == null) {cur.next = curB;}if(curB == null) {cur.next = curA;}return curN.next;

题解思路：

1.首先，判断两个链表是否为空。

2.分别给两个不同的链表定义一个头节点，curA 和 curB ，再定义一个 “傀儡” 节点curN，最后再定义一个节点 cur 从 “傀儡” 节点开始，cur用来帮助我们重新建立链表的大小链接。

3.比较 curA 和 curB 的大小，小的节点被作为 cur 重新建立顺序的一方，再让 cur 走到小节点的位置，小节点再往后走一步，直到某个链表走到尾部了。

4.最后，把走到尾部的一方链接上没走到尾部链表的curA 或者 curB 位置。最后返回 “傀儡” 节点后一个节点作为新链表的起始位置。

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。题目链接

题解代码：

ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while(cur != null) {if(cur.val < x) {//第一次if(bs == null) {bs = cur;be = cur; }else {be.next = cur;be = cur;}}else {//第一次if(as == null) {as = ae = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;}if(bs == null) {return as;}if(as == null) {return bs;}ae.next = null;be.next =as;return bs;

题解思路：

1.首先，定义空引用 bs 和 be 作为小于x 的节点存放处；定义空引用 as 和 ae 作为大于或等于 x 的节点存放处。

2.定义引用 cur ，遍历链表，若空引用 bs 和 be 或者 as 和 ae 第一次接收节点，那么把他们都赋值为第一次传过来的节点引用，后续就只让 be 或者 ae 往后走。

3.遍历完成后，分三种情况：

一是没有小于x 的部分节点，bs 和 be 还是空引用，那么直接返回 as ，也就是原链表。

二是没有大于x 的部分节点，as 和 ae 还是空引用，那么直接返回 bs，也就是原链表。

三是双方都有节点，而要把 ae 当前的节点的next置为null ；因为cur 遍历完链表的最后一个节点不知道是放在 be 还是 ae ，所以要手动把 ae 的next 置为null ，再将其两部分链接起来返回 bs

7.链表的回文结构。题目链接

题解代码：

if(A == null) {return false;} if(A.next == null) {return true;}ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;while(cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}while(A != slow) {if(A.val != slow.val) {return false;}if( A.next == slow) {return true;}A = A.next;slow = slow.next;}return true;

题解思路：

1.首先，判断链表是否为空或者链表只有一个节点的情况。

2.大体思路是将后一半的链表反转过来，再通过起始节点往后遍历与结尾节点往前遍历对比val。

3.有个特殊情况，就是链表节点个数如果为偶数的话，就需要 A.next == slow 的判断情况，，因为前面已经判断过这两个节点的val了，是相等才能走到 A.next == slow 的判断，若是这种情况，说明到中间了，直接返回 true

8.输⼊两个链表，找出它们的第一个公共结点。题目链接

题解代码：

ListNode curL = headA;ListNode curS = headB;int pl = 0;int ps = 0;while(curL != null) {pl++;curL =curL.next;}while(curS != null) {ps++;curS =curS.next;}int len = pl - ps;curL = headA;curS = headB;if(len < 0) {len = ps - pl;curL = headB;curS = headA;}while(len != 0) {curL = curL.next;len--;}while(curL != curS) {curL = curL.next;curS = curS.next;}if(curL == null) {return null;}return curS;

题解思路：

1.首先，我们假设长节点是headA，短节点是headB，再求出他们各自的链表长度，再减去得到长度差。

2.得到的长度差如果是小于零的，那么长链表是 headB,短链表是headA

3.先让长链表走 len 布，再让两个链表同时一起走，那么循环到相同节点就是他们的链表的相交节点，还要通过 curL == null 判断有没有相交，如果没相交返回null 。

9.给定⼀个链表，判断链表中是否有环。题目链接

题解代码：

 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;

题解思路：

1. 先定义一个快指针，一个慢指针。

2.每次循环，快指针走两步，慢指针走一步。

3.每次循环判断一次两个引用是否相等，如果相等说明链表存在环，若循环结束了，说明fast 走到链表尾部，该链表没有形成环。

10.给定⼀个链表，返回链表开始入环的第⼀个节点。如果链表无环，则返回 NULL 。题目链接

题解代码：

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

题解思路：

1. 先定义一个快指针，一个慢指针。

2.每次循环，快指针走两步，慢指针走一步。

3.每次循环判断一次两个引用是否相等，如果相等说明链表存在环，若循环结束了，说明fast 走到链表尾部，该链表没有形成环，返回null 。

4.存在环的情况下，看下图：

c 代表是圆环的周长，所以 head 离入环点等于 y ，所以通过上述 head 和 slow 一起走的代码即可找到入环点。

四. 模拟实现 LinkedList 的一些方法。

注意：

在Java的中LinkedList底层实现的是双向链表。

代码实现：

//任意位置插入public void addIndex(int index,int data) {int len = size();if(index < 0 || index > size()) {throw new IndexOutOfBoundsException("双向链表index位置不合法: "+index);}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = Findindex(index);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}//寻找插入节点的后一个节点public ListNode findindex(int index) {ListNode cur = head;while(index != 0) {cur = cur.next;index--;}return cur;}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {node.next = head;head.prev = node;head = node;}}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;last = node;}else {last.next = node;node.prev = last;last = node;}}

注意：

prev 是指向前一个节点，next 是指向下一个节点。

代码分析：

这里我们实现了头插法，尾插法，任意下标插入的方法。

1.头插法：

首先定义一个要插入的新节点 node ，再判断当前是不是空链表，如果是空链表，说明此时要插入的是第一个元素；如果不是空链表，再通过先绑定后面，再绑定前面的操作进行插入元素。

2.尾插法：

3.任意下标插入法：

首先，要判断准备要插入的下标是否合法，通过 size（）方法，得到链表的节点个数，如果下标不合法就抛出个异常。

其次，如果下标是 0 或者是 size（），证明是头插法或者是尾插法，调用其对应的方法就行了。

最后，findindex 方法找到准备插入新节点的后一个节点，再通过 “反C” 方法绑定。