# LeetCode 热题 HOT 100：链表专题

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

## 2. 两数相加

• 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 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 个结点

``````class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0); // 伪头部节点
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 pre.next;
}
}
``````

## 21. 合并两个有序链表

``````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 个升序链表

``````class Solution {
public ListNode mergeKLists(ListNode[] lists) {
for(int i = 0; i < lists.length; i ++){
}
}

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. 环形链表

``````public class Solution {
return false;
}
Set<ListNode> set = new HashSet(); // set 记录结点的地址
return true;
}
}
return false;
}
}
``````

``````public class Solution {
return false;
}
ListNode slow, fast;
// 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;
}
}
``````

``````public class Solution {

while(true){
if(fast==null || fast.next==null){
return false;
}
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
return true;
}
}
}
}
``````

## 142. 环形链表 II

``````public class Solution {
Set<ListNode> set = new HashSet<>();
while(p!=null){
if(set.contains(p)){
return 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 {
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. 排序链表

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

``````class Solution {
}

// 归并排序
// 将头指针和尾指针之前的元素进行排序，初始尾指针为null，即最后一个节点的下一个空节点
public ListNode mergeSort(ListNode head, ListNode tail){
}
}
ListNode slow, fast;
while(fast != tail){
slow = slow.next;
fast = fast.next;
if(fast != tail){
fast = fast.next;
}
}
ListNode mid = slow;
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;
}
}
``````

``````class Solution {
}

// 归并排序
}
ListNode slow = head; // 快慢指针

while(fast!=null && fast.next!=null){ // 查询中间节点
slow = slow.next;
fast = fast.next.next;
}

ListNode mid = slow.next; // 断链
slow.next = null;

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;
}
}
``````

``````class Solution {
ListNode pre = new ListNode(0);

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){
return null;
}
for(int i = 1; i < step && p.next!=null; i ++){
p = p.next;
}
ListNode right = p.next;
p.next = null; // 切断连接
return right;
}

// 求链表长度
int co = 0;
co++;
}
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. 相交链表

• 设不是公共部分的节点数分别是 `a、b`，公共节点数为 `n`
• 如果有公共节点，则当 `p1` 遍历完 `a+n` 个节点时，再在另一个链表的头部遍历 `b` 个节点时，必相交。原因在于此时 `p2` 遍历了 `b+n+a` 个结点。
• 如果没有公共节点部分，那么 `p1``p2` 经历了上文的步骤后，都会为 `null``null==null``true`
因此跳出循环，要么 `null == null`，要么都不为空找到了公共节点。
``````public class Solution {
while(p1 != p2){
p1 = p1 == null ? headB : p1.next;
p2 = p2 == null ? headA : p2.next;
}
return p1;
}
}
``````

## 206. 反转链表

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

## 234. 回文链表

``````class Solution {
while(p!=null){
stack.push(p);
p = p.next;
}
p = stack.pop();