LeetCode 热题 HOT 100：链表专题

LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/

---

---

2. 两数相加

题目链接：https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

实现步骤：

• 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如：987 + 23 = 987 + 023 = 1010。
• 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值。
• 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点。

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre = new ListNode(0);ListNode p1 = l1, p2 = l2, q = pre;int sign = 0;while(p1 != null || p2 != null){int sum = 0;if(p1 == null){sum = p2.val + sign;p2 = p2.next;}else if(p2 == null){sum = p1.val + sign;p1 = p1.next;}else{sum = p1.val + p2.val + sign;p1 = p1.next;p2 = p2.next;}sign = sum >= 10 ? 1 : 0; // 修改标志位ListNode node = new ListNode(sum % 10);q.next = node;q = q.next;}if(sign == 1){ListNode node = new ListNode(1);q.next = node;}return pre.next;}
}

---

19. 删除链表的倒数第 N 个结点

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre = new ListNode(0); // 伪头部节点pre.next = head;ListNode p, q;p = q = pre;int co = 0;while(q.next != null){ // 先让q指针先走n步，然后p指针再继续走if(++co > n){p = p.next;}q = q.next;}// 结束循环时，p指针指向倒数第N+1位p.next = p.next.next;// 注意避坑点：return head; 是存在问题的：当链表中只有一个元素时，p指针会进行删除后，head 还是指向原来的那个结点。return pre.next; }
}

---

21. 合并两个有序链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode res = new ListNode(0);ListNode p = res;while(list1 != null && list2 != null){if(list1.val < list2.val){p.next = list1;list1 = list1.next;}else{p.next = list2;list2 = list2.next;}p = p.next;}p.next = list1 == null ? list2 : list1;return res.next;}
}

---

23. 合并 K 个升序链表

题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode head = null;for(int i = 0; i < lists.length; i ++){head = mergeTwoLists(head, lists[i]);}return head;}public ListNode mergeTwoLists(ListNode a, ListNode b){ListNode res = new ListNode(0);ListNode p = res;while(a!=null && b!=null){if(a.val < b.val){p.next = a;a = a.next;}else{p.next = b;b = b.next;}p = p.next;}p.next = a != null ? a : b;return res.next;}
}

---

141. 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked

哈希表做法（时间复杂度较高）：

public class Solution {public boolean hasCycle(ListNode head) {if(head == null){return false;}Set<ListNode> set = new HashSet(); // set 记录结点的地址while(head.next != null){if(set.contains(head)){return true;}set.add(head);head = head.next;}return false;}
}

快慢指针做法1：

public class Solution {public boolean hasCycle(ListNode head) {if(head == null){return false;}ListNode slow, fast;slow = head;fast = head.next;// slow 每次向前走一步，fast 每次向前走两步（可以任意多步）// 当存在环时，fast 由于走得快，会发生扣圈的情况，且最终与 slow 相遇// 当不存在环时，fast 可能在某次循环后，发生当前位置为空，或下一位置为空的两种情况，当然由于走的快，最终会返回false。// 总之，循环的结束条件，要么出现环 slow == fast，要么 fast 先一步为空！ while(slow != fast && fast != null && fast.next != null){// 注意：fast != null 要先于fast.next != null 来判断，以防止控制帧异常slow = slow.next;fast = fast.next.next;}return slow == fast;}
}

快慢指针做法2（思路同下方“环形链表2”）：

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

---

142. 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked

哈希表做法（时间复杂度较高）：

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

快慢指针，实现思路如下：

• 设 fast 每次走两个节点， slow 每次走一个节点。环外有 a 个结点，环内有 b 个结点。
• 相遇时，fast 走了 f 步，slow 走了 s 步。
  ① f = 2s
  ② f = s + nb 表示 f 比 s 多走了 n*b 步，即 n 圈。这样表示的原因在于扣圈。
  化简得：f = 2nb, s = nb
• 设刚开始 slow 指针从开始到环的入口要走 k 步：k = a + nb （n = 0,1,2,…）
• 由于 s = n*b，即已经走了 n*b 步了，那么此时只需要再走 a 步即可回到链表入环的起点。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, 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; // fast回到链表起点，与 slow 一同遍历 a 步while(slow != fast){slow = slow.next;fast = fast.next;}return fast;}
}

---

148. 排序链表

题目链接：https://leetcode.cn/problems/sort-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

使用优先队列模仿堆：

class Solution {public ListNode sortList(ListNode head) {PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> b.val-a.val); // 大顶堆while(head != null){queue.offer(head); // 从堆底插入head = head.next;}ListNode pre = new ListNode(0);while(!queue.isEmpty()){ListNode p = queue.poll(); // 出队列并调整堆p.next = pre.next; // 头插法倒序pre.next = p;}return pre.next;}
}

自顶向下归并排序1： 时间复杂度 O(nlogn)，空间复杂度O(logn)

class Solution {public ListNode sortList(ListNode head) {return mergeSort(head, null);}// 归并排序// 将头指针和尾指针之前的元素进行排序，初始尾指针为null，即最后一个节点的下一个空节点public ListNode mergeSort(ListNode head, ListNode tail){if(head == tail){return head;}if(head.next == tail){ // 隔离出来单独结点head.next = null;return head;}ListNode slow, fast;slow = fast = head;while(fast != tail){slow = slow.next;fast = fast.next;if(fast != tail){fast = fast.next;}}ListNode mid = slow;ListNode l1 = mergeSort(head, mid); // 将 head 至 mid 之前的节点进行排序ListNode l2 = mergeSort(mid, tail); // 将 mid 至 tail 之前的节点进行排序return mergeList(l1, l2);}// 合并两个有序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre = new ListNode(0);ListNode p = pre;while(l1 != null && l2 != null){if(l1.val < l2.val){p.next = l1;l1 = l1.next;}else{p.next = l2;l2 = l2.next;}p = p.next;}p.next = l1 == null ? l2:l1;return pre.next;}
}

参考链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/?envType=featured-list&envId=2cktkvj%3FenvType%3Dfeatured-list&envId=2cktkvj

自顶向下归并排序2：

class Solution {public ListNode sortList(ListNode head) {return mergeSort(head);}// 归并排序public ListNode mergeSort(ListNode head){if(head==null || head.next==null){return head;}ListNode slow = head; // 快慢指针ListNode fast = head.next;while(fast!=null && fast.next!=null){ // 查询中间节点slow = slow.next;fast = fast.next.next;}ListNode mid = slow.next; // 断链slow.next = null;ListNode l1 = mergeSort(head);ListNode l2 = mergeSort(mid);return mergeList(l1, l2);}// 合并两个有序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre = new ListNode(0);ListNode p = pre;while(l1 != null && l2 != null){if(l1.val < l2.val){p.next = l1;l1 = l1.next;}else{p.next = l2;l2 = l2.next;}p = p.next;}p.next = l1 == null ? l2:l1;return pre.next;}
}

自底向上排序： 时间复杂度 O(nlog)，空间复杂度O(n)

class Solution {public ListNode sortList(ListNode head) {ListNode pre = new ListNode(0);pre.next = head;int len = getLength(head); // 获取长度for(int step = 1; step < len; step *=2){ //依次将链表分块的长度分为：1，2，4...ListNode curr = pre.next;ListNode p = pre;// p 用于链接每次分块的链表，如：第一次循环链接分块长度为1的链表，然后链接分块长度为2的链表while(curr != null){ListNode h1 = curr; // 第一块链表的头ListNode h2 = spilt(h1, step); // 第二块链表的头curr = spilt(h2, step); // 下次while循环的头，也是给到h1// 合并第一二块链表，下次while循环合并第三四块链表....ListNode res = mergeList(h1, h2);// 将合并后的链表链接起来，并将指针移到链表的最后一个节点，以链接下次的链表p.next = res;while(p.next!=null){p = p.next;}}}return pre.next;}// 分割链表，并返回后半段的链头public ListNode spilt(ListNode head, int step){if(head == null){return null;}ListNode p = head;for(int i = 1; i < step && p.next!=null; i ++){p = p.next;}ListNode right = p.next;p.next = null; // 切断连接return right;}// 求链表长度public int getLength(ListNode head){int co = 0;while(head!=null){co++;head = head.next;}return co;}// 合并两个升序链表public ListNode mergeList(ListNode l1, ListNode l2){ListNode pre = new ListNode(0);ListNode p = pre;while(l1 != null && l2 != null){if(l1.val < l2.val){p.next = l1;l1 = l1.next;}else{p.next = l2;l2 = l2.next;}p = p.next;}p.next = l1 == null ? l2:l1;return pre.next;}
}

---

160. 相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

实现步骤：

• 设不是公共部分的节点数分别是 a、b，公共节点数为 n。
• 如果有公共节点，则当 p1 遍历完 a+n 个节点时，再在另一个链表的头部遍历 b 个节点时，必相交。原因在于此时 p2 遍历了 b+n+a 个结点。
• 如果没有公共节点部分，那么 p1 与 p2 经历了上文的步骤后，都会为 null， null==null 为 true。
  因此跳出循环，要么 null == null，要么都不为空找到了公共节点。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA;ListNode p2 = headB;while(p1 != p2){p1 = p1 == null ? headB : p1.next;p2 = p2 == null ? headA : p2.next;}return p1;}
}

---

206. 反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = new ListNode(0);ListNode p = head;while(p!=null){ListNode q = p.next;p.next = pre.next;pre.next = p;p = q;}return pre.next;}
}

---

234. 回文链表

题目链接：https://leetcode.cn/problems/palindrome-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

class Solution {public boolean isPalindrome(ListNode head) {Deque<ListNode> stack = new LinkedList<>();ListNode p = head;while(p!=null){stack.push(p);p = p.next;}while(head != null){p = stack.pop();if(p.val != head.val){return false;}head = head.next;}return true;}
}

---