算法 | 第2章链表相关《程序员面试金典》#yyds干货盘点# _面试

实践是知识的母亲，知识是生活的明灯。这篇文章主要讲述算法 | 第2章链表相关《程序员面试金典》#yyds干货盘点#相关的知识，希望能为你提供帮助。
@[TOC](第2章链表相关《程序员面试金典》)
前言本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；
0. *经验总结 0.1 程序员面试金典 P79

链表的特点：无法在常数时间复杂度内访问链表的特定元素；可以在参数事件复杂度内加入和删除元素；
如果链表被多个对象引用，当链表头结点变了，可能会有一些对象仍然指向原头结点；解决方法：可以用LinkedList封装Node类，该类只包含一个成员变量：头结点；
链表问题可以关注“快慢指针”和递归； 0.2 需要询问面试官的点
是否可以修改原链表；
是否可以开辟额外空间；
时间优先还是空间优先；
在面试中要弄清单向链表和双向链表； 0.3 快慢指针
快慢指针又称双指针，是一个广泛的概念，只要涉及两个指针遍历链表，并且一前一后，都可以称为快慢指针；
快慢指针在不同题目有不同的作用，常见类型有：
- 找到中点：慢指针每走n步时，快指针走2n步，当快指针达到尾部时；
- 找到三分之一点：慢指针走n步，快指针走3n步；
- 找到倒数第x个节点：快指针先走x步后，慢指针从头出发，与快指针速度一样，当快指针达到尾部时，慢指针到倒数第k个节点；【详情见 2. 返回倒数第 k 个节点】
- 测试环形链表：慢指针每走n步时，快指针走2n步，能相遇说明环形；
- 测试链表是否成环并找到第一个成环节点：【详情见 8. 环路检测】
- …… 0.4递归
实际上所有递归算法都可以转换成迭代法，只是后者可能要复杂得多；
一般来说，递归解法更简洁，但效率低下；

1. 移除重复节点 [easy]

文章图片

1.1 考虑点

需要问清楚面试官是否可以开辟额外空间；
需要询问面试官时间优先还是空间优先；

1.2 解法 1.2.1 集合法

public ListNode removeDuplicateNodes(ListNode head) if(head == null || head.next == null) return head; ListNode cur = head; ListNode index = head; Set< Integer> set = new HashSet< > (); set.add(head.val); while( cur.next != null) cur = cur.next; if( !set.contains(cur.val) ) index.next = cur; index = cur; set.add(cur.val); else index.next = null; return head;

执行时间：66.09%；内存消耗：51.20%；
也可以用哈希表；
时间复杂度：O(N)，其中 N 是给定链表中节点的数目；
空间复杂度：O(N)。在最坏情况下，给定链表中每个节点都不相同，哈希表中需要存储所有的 N个值；

1.2.2 两循环法

public ListNode removeDuplicateNodes(ListNode head) ListNode ob = head; while (ob != null) ListNode oc = ob; while (oc.next != null) if (oc.next.val == ob.val) oc.next = oc.next.next; else oc = oc.next; ob = ob.next; return head;

执行时间：93.52%；内存消耗：93.52%；
时间复杂度：O(N^2^)，其中 N 是给定链表中节点的数目；
空间复杂度：O(1)；

2. 返回倒数第 k 个节点 [easy]

文章图片

2.1 考虑点

需要问清楚面试官是否可以开辟额外空间；

2.2 解法 2.2.1 双指针同步运动法（快慢指针）（优）

public int kthToLast(ListNode head, int k) if(head == null || head.next == null) return head.val; ListNode cur = head; ListNode index = head; //cur先走k-1个步长 for(int i = 0; i < k - 1; i++ ) cur = cur.next; //index上链表，跟cur同步运动，当cur到达链表尾时，cur为倒数第k个 while(cur.next != null) cur = cur.next; index = index.next; return index.val;

执行时间：100.00%；内存消耗：30.78%；
第一个指针先移动k步，然后第二个指针再从头开始，这个时候这两个指针同时移动，当第一个指针到链表的末尾的时候，返回第二个指针即可；

2.2.2 使用栈法

public int kthToLast(ListNode head, int k) Stack< ListNode> stack = new Stack< > (); //链表节点压栈 while (head != null) stack.push(head); head = head.next; //在出栈串成新的链表 ListNode firstNode = stack.pop(); while (--k > 0) ListNode temp = stack.pop(); temp.next = firstNode; firstNode = temp; return firstNode.val;

执行时间：9.00%；内存消耗：58.84%；
把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈，出栈的结点重新串成一个新的链表即可；

2.2.3 递归

int size; public int kthToLast(ListNode head, int k) if (head == null) return 0; int value = https://www.songbingjia.com/android/kthToLast(head.next, k); if (++size == k) return head.val; return value;

执行时间：100.00%；内存消耗：24.44%；
递归访问整个链表，到达尾部时，回传一个设置为0的size计数器，后续调用每次都会将计数器加1，当计数器为k是，即为倒数第k个。value为暂存的结果值；

3. 删除中间节点 [easy]

文章图片

3.1 考虑点

题目有点“脑筋急转弯”的意思，注意给出的是当前要删除的节点；
面试官期待的是：当待删除的节点为链表尾节点时的情况：
- 因为不能访问前一个节点，要从其他方面考虑解决方法；
- 可以考虑将该节点标记为假节点，即物理上存在，逻辑上不在；

3.2 解法 3.2.1 复制自己法

public void deleteNode(ListNode node) if(node == null || node.next == null) return; ListNode nextNode = node.next; node.val = nextNode.val; node.next = nextNode.next;

执行时间：100.00%；内存消耗：72.05%；
如果只能访问当前节点，那么该题的解题思路就是，将自己变成其他节点；
- 举个例子：A-> B-> C-> D；
- 如果要删掉 B 节点，那么只需要将 B 变为 C，再把 B 的指针指向 D，即可完成；

4. 分割链表 [medium]

文章图片

4.1 考虑点

注意题目意思，可以排序，但不一定是排序；
如果本题描述的是数组，对于如何移动元素要谨慎，数组元素的移动通常开销很大。但链表相对比较简单；

4.2 解法 4.2.1 双指针逐个处理法

public ListNode partition(ListNode head, int x) if(head == null || head.next == null ) return head; //找到比x小的节点，该节点离x节点最近 ListNode index = head; while(index.val < x & & index.next != null) index = index.next; //用2个指针完成移位操作 //index为首个大于等于x的节点 //cur为index2的next ListNode cur = index.next; while(index.next != null) if(cur.val > = x) //继续 index = index.next; cur = cur.next; else //移位 index.next = cur.next; if( head.val < x) cur.next = head.next; head.next = cur; else cur.next = head; head = cur; cur = index.next; return head;

执行时间：100.00%；内存消耗：64.81%；

4.2.2 排序法

public ListNode partition(ListNode head, int x) return sortList(head, null); private ListNode sortList(ListNode head, ListNode tail) //无法继续拆分的情况 if (head == null) return null; //无法继续拆分的情况 if (head.next == tail) head.next = null; return head; //快慢指针找到中间节点 ListNode slow = head, fast = head; while (fast != tail & & fast.next != tail) slow = slow.next; fast = fast.next.next; ListNode mid = slow; //左边继续拆分 ListNode left = sortList(head, mid); //右边继续拆分 ListNode right = sortList(mid, tail); //有序链表合并 return merge(left, right); private ListNode merge(ListNode left, ListNode right) ListNode mergeNode = new ListNode(); ListNode help = mergeNode; //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点 while (left != null & & right != null) if (left.val < right.val) help.next = left; left = left.next; else help.next = right; right = right.next; help = help.next; //最后如果有剩余的节点，就一次性链上去 help.next = left == null ? right : left; return mergeNode.next;

执行时间：100.00%；内存消耗：83.65%；
最无脑的做法是排序，这题不管x给什么，只需要对链表进行一次排序，既能满足题目要求，之前的题目中有练习过插入排序、归并排序，随便哪一种都可以，当然归并的效率更高一点；

4.2.3 头插法

public ListNode partition(ListNode head, int x) ListNode dummy = new ListNode(); dummy.next = head; while (head != null & & head.next != null) int nextVal = head.next.val; if (nextVal < x) ListNode next = head.next; head.next = head.next.next; next.next = dummy.next; dummy.next = next; else head = head.next; return dummy.next;

执行时间：100.00%；内存消耗：20.44%；
逐个遍历，遇到小于x值的节点，就插到头部；
PS：java中HashMap，jdk1.8之前，扩容时链表采用的就是头插法（存在死循环的问题，1.8改了）；

4.2.4 原地删除

public ListNode partition(ListNode head, int x) ListNode dummy = new ListNode(); dummy.next = head; ListNode smallDummy = new ListNode(); ListNode small = smallDummy; //和删除节点的套路一样，先处理头节点满足条件的情况 while (head != null) if (head.val > = x) break; small.next = new ListNode(head.val); small = small.next; head = head.next; //删除 ListNode cur = head; ListNode pre = null; while (cur != null) if (cur.val < x) pre.next = cur.next; small.next = new ListNode(cur.val); small = small.next; else pre = cur; cur = cur.next; small.next = head; return smallDummy.next;

执行时间：100.00%；内存消耗：56.22%；
按照删除节点的方式，遇到小于x值的节点，就从原链表中删除，并添加到新的链表中，这样一次遍历结束后，只要把新的链表连上原链表即可；

5. 链表求和 [medium]

文章图片

5.1 考虑点

需要考虑链表长度不一导致的空指针异常问题；
进阶的思考：
- 链表长度不一时的对位问题，如（1 -> 2 -> 3 -> 4）和（5 -> 6 -> 7），这里5对2而不是1；
- 上述问题可以遍历链表，用0占位解决；

5.2 解法 5.2.1 反向存放法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) if( l1 == null & & l2 == null) return null; ListNode cur1 = l1; ListNode cur2 = l2; int cache = 0; boolean isFirst = true; ListNode head = null; ListNode index = null; while( cur1 != null || cur2 != null) //加法 int value = https://www.songbingjia.com/android/0; if( cur1 == null) value = cur2.val + cache; cur2 = cur2.next; else if ( cur2 == null) value = cur1.val + cache; cur1 = cur1.next; else value = cur1.val + cur2.val + cache; cur1 = cur1.next; cur2 = cur2.next; //进位在cache储存 cache = value / 10; //构造新节点，新节点指向新节点 ListNode node = new ListNode(value%10); if(isFirst) head = node; index = node; isFirst = false; else index.next = node; index = node; //判断cache if(cache != 0) ListNode node = new ListNode(cache); index.next = node; return head;

执行时间：97.51%；内存消耗：33.72%；
通常做法：逐个遍历，进位，构建新节点；

5.2.2 递归法

public ListNode addTwoNumbers(ListNode l1, ListNode l2) ListNode head = new ListNode(0); helper(head, l1, l2, 0); return head.next; private void helper(ListNode result, ListNode l1, ListNode l2, int carry) if (l1 == null & & l2 == null & & carry == 0) return; int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry; result.next = new ListNode(0); result.next.val = sum % 10; carry = sum / 10; helper(result.next, l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);

执行时间：100.00%；内存消耗：26.25%；

6. 回文链表 [easy]

文章图片

6.1 考虑点

对于链表，可以思考的角度有：改变链表方向、拼接、成环等；
需要问清楚面试官是否可以开辟额外空间；
需要问清楚面试官是否可以修改链表；

6.2 解法 6.2.1 改变方向双向遍历法（优）

public boolean isPalindrome(ListNode head) if(head == null) return true; //统计链表长度 ListNode cur = head; int count = 0; while( cur != null ) count++; cur = cur.next; if( count < 2) return true; //改变前 count/2-1 个节点指向，分奇偶讨论 ListNode right = head; //定位right指针 if( count % 2 == 1 ) //奇数情况 for( int i = 0; i < count/2+1; i++) right = right.next; else //偶数情况 for( int i = 0; i < count/2; i++) right = right.next; //改变前count/2-1个节点方向 ListNode left = head; cur = head.next; ListNode mid = cur.next; //判断对只有2~3个节点单独判断 if(count < 4) return left.val == right.val; for( int i = 0; i < count/2-1; i++) cur.next = left; left = cur; cur = mid; mid = mid.next; //遍历比较left和right while(right != null) if(left.val != right.val) return false; right = right.next; left = left.next; return true;

执行时间：96.85%；内存消耗：80.19%；
不使用额外空间；
需要注意，是否可以改变原链表；

6.2.2 将值复制到数组中后用双指针法

public boolean isPalindrome(ListNode head) List< Integer> vals = new ArrayList< Integer> (); // 将链表的值复制到数组中 ListNode currentNode = head; while (currentNode != null) vals.add(currentNode.val); currentNode = currentNode.next; // 使用双指针判断是否回文 int front = 0; int back = vals.size() - 1; while (front < back) if (!vals.get(front).equals(vals.get(back))) return false; front++; back--; return true;

执行时间：32.69%；内存消耗：24.77%；
时间复杂度：O(n)，其中 n 指的是链表的元素个数；
- 第一步：遍历链表并将值复制到数组中，O(n)。
- 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
- 总的时间复杂度：O(2n) = O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值；
需要开辟额外空间；

6.2.3 递归

private ListNode frontPointer; private boolean recursivelyCheck(ListNode currentNode) if (currentNode != null) if (!recursivelyCheck(currentNode.next)) return false; if (currentNode.val != frontPointer.val) return false; frontPointer = frontPointer.next; return true; public boolean isPalindrome(ListNode head) frontPointer = head; return recursivelyCheck(head);

执行时间：56.10%；内存消耗：5.05%；
时间复杂度：O(n)，其中 n 指的是链表的大小；
空间复杂度：O(n)，其中 n 指的是链表的大小。这种方法不仅使用了 O(n)的空间，且比第一种方法更差，因为在许多语言中，堆栈帧的开销很大（如 python），并且最大的运行时堆栈深度为 1000（可以增加，但是有可能导致底层解释程序内存出错）。为每个节点创建堆栈帧极大的限制了算法能够处理的最大链表大小；

7. 链表相交 [easy]

文章图片

7.1 考虑点

这里不能使用链表反转，题目要求不能破坏原有结构；
对于两条长度不同的链表而言，可以先遍历求出各自的长度再做计算，也可以使用；两个指针走完两条链表，最后必然能重合，因为指针的速度（步长）的一样的；
需要问清楚面试官是否可以开辟额外空间；

7.2 解法 7.2.1 长度对齐双指针法

public ListNode getIntersectionNode(ListNode headA, ListNode headB) if( headA == null || headB == null ) return null; ListNode cur = headA; int countA = 0; while( cur != null ) countA++; cur = cur.next; cur = headB; int countB = 0; while( cur != null) countB++; cur = cur.next; //保证headA长于headB if( countA < countB) return getIntersectionNode(headB,headA); ListNode curA = headA; ListNode curB = headB; for( int i = 0; i < countA-countB; i++) curA = curA.next; while( curA != null ) if( curA.equals(curB) ) return curA; curA = curA.next; curB = curB.next; return null;

执行时间：100.00%；内存消耗：57.18%；
时间复杂度：O(A+B)，A和B是两个链表的长度；
空间复杂度：O(1)；

7.2.2 双指针（优）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) ListNode h1 = headA; ListNode h2 = headB; while(h1 != h2) h1 = (h1 == null ? headB : h1.next); h2 = (h2 == null ? headA : h2.next); return h1;

执行时间：100.00%；内存消耗：57.18%；
对于h1来说，走到末尾（或相交点）时，走了两段链表（两段链表不同部分）的路径；
对于h2来说，走到末尾（或相交点）时，走了两段链表（两段链表不同部分）的路径；
h1和h2走过的路径相同，因此第二轮就能匹配到；

8. 环路检测 [medium]

文章图片

8.1 考虑点

处理环形链表可以试试快慢指针；

8.2 解法 8.2.1 快慢指针法（优）

public ListNode detectCycle(ListNode head) if( head == null ) return null; if(head.next == null) return null; if(head.next.next == null) return null; //使用快慢指针找到有count个环成圈; ListNode fast = head.next.next; ListNode slow = head.next; int count = 1; //count变量不是必要的 while( fast != slow ) if(fast == null || slow == null) return null; slow = slow.next; if(fast.next != null) fast = fast.next.next; else return null; count++; // cur 和 slow 一起走，走n步到环路开头节点 ListNode cur = head; while( cur != slow ) cur = cur.next; slow = slow.next; return cur;

执行时间：100.00%；内存消耗：53.71%；
时间复杂度：O(n)，n为不成环的节点和成环节点的较大值；
空间复杂度：O(1)，不开辟额外空间，算法中的count不是必要的；
算法解释：算法主要分为两个部分，如下：
- 使用快慢指针找到有count个环成圈：走x步到达下标为x的节点。可以通过快慢指针获得count（或count的质因数）个节点成圈，同时慢指针走了count步（此时快慢指针所指节点下标为count）。假设环路开头节点的下标为 n（n< =count），从链表头走要走n步到环路开头节点；
- 走n步到环路开头节点：从链表头到快慢指针处走count步，从链表头到环路开头节点要n步。如果要从环路开头节点走到快慢指针处要走count-n步；如果要从环路开头节点再一次回到开头节点必须走完一个圈（或n圈），即走count步。那么从快慢指针处走到开头节点至少就要count-(count-n)=n步，而我们从链表头走到环路开头节点也是要走n步；

8.2.2 哈希表

public ListNode detectCycle(ListNode head) ListNode pos = head; Set< ListNode> visited = new HashSet< ListNode> (); while (pos != null) if (visited.contains(pos)) return pos; else visited.add(pos); pos = pos.next; return null;