面试笔试中链表的题目都比较死，几种类型反复做反复记忆就好了

本文整理了面试高频的十二个链表相关的算法题，覆盖了几乎所有常考的情况
刷熟了这几个题，再遇到手撕链表题就没太大压力了！

本文的每个标题都是leetcode中国站的直达链接，如果想要动手试一试就点击进去吧

本文的所有代码均为我学习了大量题解后写出的的较为优美的代码，推荐反复观看记忆

环形链表


本题是典型的快慢指针法应用题，比较容易想到的就是采用额外的空间进行存储，如解法一的set存储。但是最经典的解法还是采用快慢指针，可以一次遍历并且不使用额外的空间，面试时使用快慢指针会是一个大的亮点

解法一：Hash查找法 

public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> set = new HashSet<ListNode>(); ListNode node = head; while (node != null) { if (set.contains(node)) { return true; } set.add(node); node = node.next; } return false; } }

解法二：快慢指针法（推荐） 

public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode fast = head.next; ListNode slow = head; while (fast != slow) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } }

环形链表II


本题同样是对快慢指针法的典型应用，相比第一题更为巧妙，尽量理解，如果实在不能理解可以采用记忆，记住结论就好了

解法一：Hash记录法 

public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> set = new HashSet<ListNode>(); ListNode cur = head; while (cur != null) { if (set.contains(cur)) { return cur; } set.add(cur); cur = cur.next; } return null; } }

解法二：快慢指针法（推荐）

思路：

  • 先和环形链表I一样判断有没有环，有才进行第二步
  • 从同一起点开始，fast一次走两步，slow一次走一步，当他们相遇之后，fast回到原点一次走一步，第二次相遇节点就是环连接点
  • 我的理解：
    • 就假设最简单的第二圈发生第一次相遇，第二圈走完了就第二次相遇了
    • 第一次相遇时fast走了F+(a+b)+a
    • slow走了F+a
    • 因为fast是slow的两倍速度，所以第二次相遇时fast=2*slow
    • 第二次相遇slow走了F+a+b
    • 那么fast要走2F+2a+2b,还差F+b
    • 所以就假设fast以一倍的速度陪slow走完b，另一倍速从F出发，当fast与slow相遇时，相当于fast走过了b+F 
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (true) { if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break; } fast = head; //第二阶段，找环接入点 while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }

合并两个有序链表


要点：

  • 保留一个pre标记，让一个新的指针去遍历
  • 一次遍历结束后注意只有一个链表遍历完了，还应该在结尾加上没有遍历完的链表 
public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode cur = pre; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; cur = cur.next; l1 = l1.next; } else { cur.next = l2; cur = cur.next; l2 = l2.next; } } //如果l1空了，就把l2接上去 if (l1 == null) { cur.next = l2; } else { cur.next = l1; } return pre.next; } }

反转链表


反转链表如果没有训练过可能不太好想象到，所以需要反复的多刷几次，动手多画一画
反转链表非常重要！！！！ 在复杂的程序设计题中常作为一个小的部分，如后面的回文链表

原地反转比较好想到，递归就太妙了，建议就记住原地反转就好了，容易理解记忆

迭代法：原地反转（推荐） 

public class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }

递归：

public class Solution { public ListNode reverseList(ListNode head) { //递归终止条件 if (head == null || head.next == null) { return head; } //下探 ListNode cur = reverseList(head.next); head.next.next = head; head.next = null; //每一次都返回最后一个节点 return cur; } }

图片引自leetcode题解

两两交换链表中的节点


两两交换也是很重要的一类题型，推荐熟练的写迭代的方式，并掌握原理，如果进阶可能会是交换多个结点或者以交换n个结点作为程序的一部分

解法一：递归（看别人写递归觉得自己就是傻子） 

public class Solution { //每次看人家写递归都觉得自己像个傻子，看得懂想不到 public ListNode swapPairs(ListNode head) { if (head == null || head.next == null) { return head; } ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; } }

解法二：迭代（推荐） 

class Solution { public ListNode swapPairs(ListNode head) { ListNode node = new ListNode(-1); node.next = head; ListNode pre = node; while (pre.next != null && pre.next.next != null) { ListNode l1 = pre.next, l2 = pre.next.next; ListNode next = l2.next; l1.next = next; l2.next = l1; pre.next = l2; pre = l1; } return node.next; } }

相交链表



本题的要点就是交替遍历两条路

已上图为例，一条路径遍历a-c-b，另一条遍历b-c-a
当两条路径遍历相遇时，就是交点 

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode node1 = headA; ListNode node2 = headB; while (node1 != node2) { node1 = node1 == null ? headB : node1.next; node2 = node2 == null ? headA : node2.next; } return node1; } }

删除排序链表中的重复元素


迭代实现（推荐） 

public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; ListNode node = head; while (node.next != null && node != null) { if (node.val == node.next.val){ node.next = node.next.next; }else { node = node.next; } } return head; }

递归实现： 

public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.val == head.next.val ? head = head.next : head; }

删除链表的倒数第N个节点


本题也运用到了快慢指针，说明快慢指针在链表题中的地位

本题思路：

  • 移动快指针n步，使快慢指针步差为n
  • 如果此时快指针为null，说明要删除的节点是头结点，直接返回head.next;
  • 如果快指针不是null，那么就通过快慢指针查找到倒数第k+1个节点
  • 然后删除掉倒数第k个节点

一趟扫描：快慢指针法 

public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if (head == null || head.next == null) return null; ListNode fast = head; ListNode slow = head; //将fast和slow的步调差调成n，当fast到达末尾了，slow到达指定节点 while (n > 0) { fast = fast.next; n--; } //倒数的数就是头结点的情况，此时fast是null if (fast == null){ return head.next; } //倒数的数不是头结点，按顺序移动fast和slow节点，直到倒数第二个，测试slow节点到达删除节点的上一个 while (fast.next != null) { fast = fast.next; slow = slow.next; } //slow是待删除节点上一个节点，删除slow.next节点 slow.next = slow.next.next; return head; } }

两数相加II


非常非常经典高频的考题，如果没有练过真的很难想象，一定要记得大致的步骤

  • 遍历链表，将值分别压入栈中
  • 获取的栈顶元素就是同一位的元素了，如果有就直接出栈获取，如果没有就为0
  • 计算两个值与进位数的和为sum
  • 让sum对10求模得本位的数
  • 让sum对10整除得进位数
  • 用本位数创建一个节点插入到链表头（pre.next） 
public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //初始化stack Stack<Integer> stack1 = buildStack(l1); Stack<Integer> stack2 = buildStack(l2); //新建个前驱结点方便返回 ListNode pre = new ListNode(-1); int carry = 0;//进位数 while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) { int x = stack1.isEmpty() ? 0 : stack1.pop(); int y = stack2.isEmpty() ? 0 : stack2.pop(); int sum = x + y + carry; ListNode node = new ListNode(sum % 10);//计算出本位的值 //将node插入到头结点 node.next = pre.next; pre.next = node; //计算是否有进位数 carry = sum / 10; } return pre.next; } private Stack<Integer> buildStack(ListNode head) { ListNode node = head; Stack<Integer> stack = new Stack<>(); while (node != null) { stack.push(node.val); node = node.next; } return stack; } }

回文链表


O(n) 时间复杂度和 O(1) 空间复杂度解法：

  • 快慢指针找到中点
  • 将链表分割为两部分
  • 选择后一半进行翻转
  • 翻转后再次比较 
public class Solution { /** * 快慢指针找到中点 * 选择一半进行翻转 * 翻转后再次比较 */ public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } if (fast != null) slow = slow.next;//偶数个结点，让slow指向下一个，作为后半段的开头 //将链表分为以head和slow开头的等长的两段 cut(head, slow); return isEqual(head, reverse(slow)); } //翻转链表 private ListNode reverse(ListNode head) { ListNode newHead = null; while (head != null) { ListNode tmp = head.next; head.next = newHead; newHead = head; head = tmp; } return newHead; } //判定两个链表是否相等 private boolean isEqual(ListNode head1, ListNode head2) { while (head1 != null && head2 != null) { if (head1.val != head2.val) return false; head1 = head1.next; head2 = head2.next; } return true; } //分割链表 private void cut(ListNode head, ListNode slow) { while (head.next != slow) { head = head.next; } head.next = null; } }

奇偶链表


思路：奇数放一个链表，偶数放一个链表，最后两个链表连接起来 

public class Solution { public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) return head; ListNode odd = head;//奇数节点 ListNode even = head.next;//偶数节点 ListNode evenHead = even;//暂存一个偶数节点头，方便重组完进行连接 while (even != null && even.next != null) { odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next; } //奇数链表后接上偶数链表 odd.next = evenHead; return head; } }

分割链表


思路：

  • 统计链表长度
  • 长度小于等于k，每个子链表放一个节点
  • 长度大于k，计算每个子链表长度，分割链表 
public class Solution { public ListNode[] splitListToParts(ListNode root, int k) { if (root == null) return new ListNode[k]; ListNode cur = root; int count = 0; //统计节点数 while (cur != null) { count++; cur = cur.next; } ListNode[] nodes = new ListNode[k]; cur = root; //每个子链表不超过1个节点 if (count <= k) { for (int i = 0; i < count; i++) { nodes[i] = new ListNode(cur.val); cur = cur.next; } } else { //计算每个子链表的节点数 int remain = count % k; int preCount = count / k; //记录每部分的节点个数 int[] counts = new int[k]; for (int i = 0; i < k; i++) { //前remain个链表长度为precount+1 counts[i] = remain-- > 0 ? preCount + 1 : preCount; } //遍历链表，存储元素 for (int i = 0; i < k; i++) { //初始化子链表的头结点和个数 int num = counts[i]; nodes[i] = cur; while (--num > 0) { cur = cur.next; } //截断链表 ListNode tmp = cur.next; cur.next = null; cur = tmp; } } return nodes; } }