【LeetCode Hot100 链表（上）】相交链表、反转链表、回文链表、环形链表、合并两个有序链表、两数相加
链表
- 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)，其中
-
空间复杂度：
- 由于使用了哈希集合来存储链表节点，因此空间复杂度为 O(n)，其中
n是链表的长度。
- 由于使用了哈希集合来存储链表节点，因此空间复杂度为 O(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; // 返回结果链表的头节点
}
}