【LeetCodeHot100链表（上）】相交链表、反转链表、回文链表、环形链表、合并两个有序链表、两数相加

链表 1. 相交链表问题描述解决思路代码实现 2. 反转链表问题描述解决思路代码实现 3. 回文链表问题描述解决思路代码实现 4. 环形链表问题描述解决思路代码实现 5. 环形链表II问题描述解决思路代码实现 6. 合并两个有序链表问题描述解决思路代码实现 7. 两数相加问题描述解决思路代码实现

1. 相交链表 问题描述

给定两个单链表 headA 和 headB，它们可能在某个节点相交。请编写一个函数来查找它们的第一个交点。若没有交点，返回 null。

解决思路

计算链表的长度：首先，遍历两个链表，分别计算它们的长度 lenA 和 lenB。

调整起始点：确定较长链表的起始位置，使得两个链表的剩余部分长度相同。通过让较长链表先走长度差步，保证两个链表在相同的“距离剩余部分”的起点上对齐。

同步遍历：同步遍历两个链表，如果它们的当前节点相同，则返回该节点作为交点。如果遍历结束都没有找到交点，返回 null。

代码实现 public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = 0, lenB = 0; ListNode curA = headA; ListNode curB = headB; // 计算链表A和B的长度 while (curA != null) { lenA++; curA = curA.next; } while (curB != null) { lenB++; curB = curB.next; } curA = headA; curB = headB; // 让curA为最长链表的头，lenA为其长度 if (lenB > lenA) { // 交换（lenA, lenB） int tmpLen = lenA; lenA = lenB; lenB = tmpLen; // 交换（curA, curB） ListNode tmpNode = curA; curA = curB; curB = tmpNode; } // 求长度差 int gap = lenA - lenB; // 让curA和curB在同一起点上（末尾位置对齐） while (gap-- > 0) { curA = curA.next; } // 现在在同一起点上同步遍历 while (curA != null) { if (curA == curB) return curA; // 找到交点 curA = curA.next; curB = curB.next; } return null; // 没有交点 } } 2. 反转链表 问题描述

给定一个单链表的头节点 head，请编写一个函数来反转该链表，并返回反转后的链表。

解决思路

初始化：

创建三个指针：cur 指向当前节点，pre 指向前一个节点，temp 用来暂存当前节点的下一个节点。

反转操作：

遍历链表的每个节点。在遍历过程中，将当前节点的 next 指针指向前一个节点，从而实现链表的反转。使用 cur.next = pre 将当前节点与前一个节点连接，然后将 pre 更新为当前节点，cur 更新为下一个节点。

结束遍历：

当 cur 为 null 时，遍历结束，此时 pre 就是反转后的链表的头节点。

返回结果：

返回 pre，即反转后的链表的头节点。 代码实现 public class Solution { public ListNode reverseList(ListNode head) { ListNode cur = head; // 当前节点 ListNode pre = null; // 前一个节点 ListNode temp = null; // 临时节点，保存当前节点的下一个节点 while (cur != null) { temp = cur.next; // 暂存当前节点的下一个节点 cur.next = pre; // 反转当前节点的指针 pre = cur; // 移动前一个节点指针 cur = temp; // 移动当前节点指针 } return pre; // 返回反转后的链表头节点 } } 3. 回文链表 问题描述

给定一个单链表的头节点 head，判断该链表是否为回文链表。回文链表是指从前往后和从后往前读的链表内容一致。

解决思路

寻找链表的中间节点：

使用快慢指针法，快指针 fast 每次移动两步，慢指针 slow 每次移动一步。当快指针到达链表末尾时，慢指针正好指向链表的中间节点。

反转链表的后半部分：

从中间节点开始，将链表的后半部分反转，这样就能方便地和前半部分进行比较。

比较前半部分和反转后的后半部分：

比较链表的前半部分和反转后的后半部分的节点值。如果有任何不相等的节点，说明链表不是回文链表。

返回结果：

如果没有发现不相等的节点，说明链表是回文的。 代码实现 public class Solution { public boolean isPalindrome(ListNode head) { // 找到中间节点，把后半部分反转，然后比较 ListNode middle = getMiddle(head); ListNode head2 = reverseList(middle); // 获得的反转链表长度只有原来的一半, 所以这里用head2来做循环停止条件 while (head2 != null) { if (head.val != head2.val) { return false; } head = head.next; head2 = head2.next; } return true; } // 快慢指针，找到链表的中间节点 public ListNode getMiddle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 反转链表 public ListNode reverseList(ListNode head) { ListNode p = null; ListNode q = head; while (q != null) { ListNode tmp = q.next; q.next = p; p = q; q = tmp; } return p; } } 4. 环形链表 问题描述

给定一个单链表 head，判断该链表是否有环。若链表中存在环，则返回 true；否则返回 false。

解决思路

使用 快慢指针（Floyd’s Cycle Detection Algorithm，也叫快慢指针法）来判断链表中是否有环。具体步骤如下：

初始化指针：

使用两个指针，慢指针 slow 每次向后移动一步，快指针 fast 每次向后移动两步。

循环遍历链表：

每次移动慢指针和快指针，直到快指针到达链表的末尾（即没有环的情况）。如果快指针和慢指针相遇，则说明链表中存在环。

处理特殊情况：

如果链表为空或者只有一个节点时，直接返回 false，因为没有环。 代码实现 public class Solution { public boolean hasCycle(ListNode head) { // 特殊情况判断：链表为空或只有一个节点 if (head == null || head.next == null) { return false; } ListNode slow = head; // 慢指针 ListNode fast = head.next; // 快指针 // 快慢指针遍历链表 while (slow != fast) { // 如果快指针到达链表末尾，则说明没有环 if (fast == null || fast.next == null) { return false; } // 移动慢指针和快指针 slow = slow.next; fast = fast.next.next; } // 快慢指针相遇，说明有环 return true; } } 5. 环形链表II 问题描述

给定一个链表，如果链表中存在环，返回环的起始节点；否则，返回 null。

解决思路

使用哈希集合：

我们可以通过遍历链表并将每个节点存储到一个哈希集合中。如果某个节点已经存在于集合中，则说明链表有环，返回该节点。如果链表没有环，那么遍历完链表所有节点后，集合不会重复任何元素，最终返回 null。

时间复杂度：

每个节点最多会被访问一次，因此时间复杂度是 O(n)，其中 n 是链表的长度。

空间复杂度：

由于使用了哈希集合来存储链表节点，因此空间复杂度为 O(n)，其中 n 是链表的长度。 代码实现 public class Solution { public ListNode detectCycle(ListNode head) { // 用哈希集合来记录访问过的节点 Set<ListNode> seen = new HashSet<>(); // 遍历链表 while (head != null) { // 如果当前节点已经出现过，说明存在环，返回当前节点 if (!seen.add(head)) { return head; } // 将当前节点的下一个节点继续遍历 head = head.next; } // 链表没有环，返回null return null; } } 6. 合并两个有序链表 问题描述

给定两个有序链表 list1 和 list2，将它们合并成一个有序链表，并返回新的链表。

解决思路

我们可以使用一个虚拟的头节点 head3，通过逐步遍历 list1 和 list2，按顺序将它们的节点加入到新链表中。

虚拟头节点：通过引入虚拟头节点，简化了合并操作，避免了在合并过程中的特殊情况处理（例如初始时没有头节点）。遍历两个链表：同时遍历两个链表，比较它们的节点值，将较小的节点加入新链表。处理剩余节点：在某一链表遍历结束后，直接将新链表的尾部指向另一个链表的剩余部分。返回结果：最终返回虚拟头节点的 next，即合并后的链表。 代码实现 public class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head3 = new ListNode(); // 虚拟头节点 ListNode cur = head3; // 当前指针，指向新链表的尾部 // 同时遍历两个链表，直到其中一个链表为空 while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; // 移动 list1 指针 } else { cur.next = list2; list2 = list2.next; // 移动 list2 指针 } cur = cur.next; // 移动当前指针 } // 合并后，只有一个链表可能没有遍历完，直接将未遍历完的链表接到新链表的末尾 cur.next = (list1 == null) ? list2 : list1; // 返回新链表的头节点 return head3.next; } } 7. 两数相加 问题描述

给定两个非空链表，表示两个非负整数。数字按逆序存储，每个节点包含一个数字。将这两个数相加，返回一个新的链表表示它们的和。

解决思路

模拟逐位相加：

从两个链表的头节点开始，对应位的数值相加。若有进位，则加到下一位。如果某个链表已经遍历完，认为它对应的数为0，继续计算。最后，如果仍有进位，需要在链表末尾添加一个新的节点。

进位处理：

进位通过 carry 变量来管理，逐位传递到下一个节点。

链表结构：

使用一个虚拟链表（通过 head 和 tail）来构建结果链表。 代码实现 public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode head = null, tail = null; // 用于构建结果链表 int carry = 0; // 进位 // 遍历链表，直到两个链表都为空 while (l1 != null || l2 != null) { // 如果某个链表到达末尾，则认为该链表对应的值为0 int n1 = (l1 != null) ? l1.val : 0; int n2 = (l2 != null) ? l2.val : 0; int sum = n1 + n2 + carry; // 计算当前位的和（包含进位） // 如果是第一个节点 if (head == null) { head = new ListNode(sum % 10); // 取个位数作为新节点 tail = head; // `tail` 指向新节点 } else { tail.next = new ListNode(sum % 10); // 创建新节点并添加到链表 tail = tail.next; // 更新 `tail` 指针 } carry = sum / 10; // 计算进位，传递到下一个节点 // 移动到下一个节点 if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } // 如果最终有进位，添加一个新节点 if (carry > 0) { tail.next = new ListNode(carry); } return head; // 返回结果链表的头节点 } }