【链表】【简单】相交/反转/回文/环形/合并有序链表

文章目录

• 1.相交链表
• • 题目
  • 解题思路：双指针
• 2.反转链表
• • 题目
  • 解题思路：指向反转（迭代法）⭐
  • 解题思路：从前向后递归翻转（递归法）
• 3.回文链表
• • 题目
  • 解题思路：数组存储
  • 解题思路：快慢指针+反转链表⭐
• 4.环形链表
• • 题目
  • 解题思路：快慢指针
  • 扩展：环形链表 II
• 5.合并两个有序链表
• 题目
• • 解题思路：双指针比较

1.相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal – 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA – 第一个链表 listB – 第二个链表 skipA – 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB – 在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at ‘8’ 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 注意：请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2： 输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at ‘2’ 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3： 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：No intersection 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。

提示： listA 中节点数目为 m listB 中节点数目为 n 1 <= m, n <= 3 * 10^4 1 <= Node.val <= 10^5 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解题思路：双指针

• A 链表独有部分长度 = a
• B 链表独有部分长度 = b
• 公共部分长度 = c

• 设置两个指针 pA 和 pB
• 让 pA 走完 A 后再走 B，当第二遍走到相交节点的时候，走过的长度为 a+c+b
• 让 pB 走完 B 后再走 A，当第二遍走到相交节点的时候，走过的长度为 b+c+a
• 也就是说两个指针在第二遍走到相交节点时的路径长度一样，此时如果两指针相等，就判定为相交节点，如果都指向空（c=0）两指针都指向末尾，此时就没有相交节点

要么两个指针每次逐步向后移动一位，直到判定为相等（此时相交节点） 第一次遍历如果其中有指针指向null，就变换为另一条的头节点 第二次便利两个同时指向null，判定为不相交 经过两次遍历后，要么都指向null，要么相交指向同一个相交节点 如果两个链表长度相同，即a=b，那第一次遍历的时候就能找到了

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA;
ListNode pB = headB;
while(pA!=pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}

2.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2： 输入：head = [1,2] 输出：[2,1]

示例 3： 输入：head = [] 输出：[]

提示： 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：指向反转（迭代法）⭐

考虑三个指针

• pre ：已经反转好的部分
• cur ：当前正在处理的节点
• next ：提前保存 cur 后面的节点

null 1 → 2 → 3 → 4 → 5 → null
↑ ↑ ↑
pre cur next

此时处理第一个节点，将1的下一个指向设置为null

null ← 1 2 → 3 → 4 → 5 → null
↑ ↑ ↑
pre cur next

null ← 1 2 → 3 → 4 → 5 → null
↑ ↑ ↑
pre cur next

处理完成后，原来cur的位置变为pre，原来next即变成下一个要处理的节点cur。直到处理到末尾，即next = null，此时返回当前节点为头节点

public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
//考虑为[]的情况，此时没有next,cur为null
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

不能直接拷贝value值进行反转，这样只是修改了节点存储的数据，并没有改变节点之间的 next 指向。反转链表本质上是反转节点之间的连接关系。

解题思路：从前向后递归翻转（递归法）

从后向前处理节点，当第一次调用reverseList(1)，后续会递归到reverseList(2)、reverseList(3)，

node1
↓
[1] → [2] → [3]

到3之后，返回为null，此时开始处理reverseList(2)，此时叫 3.next=2 ，2.next=null，

2 → 3 → null
↑ ↓
└───┘

在递归到1节点，2.next=1,1.next=null

1 → 2 ← 3
↑ ↓
└───┘

public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

3.回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1： 输入：head = [1,2,2,1] 输出：true

示例 2： 输入：head = [1,2] 输出：false

提示： 链表中节点数目在范围[1, 10^5] 内 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路：数组存储

将链表中的数值存储到数组中，然后在数组中设置左右指针进行比较。 空间复杂度：O(n)

public boolean isPalindrome(ListNode head) {
int[] arr = new int[100000];
int i = 0;
while(head!=null){
arr[i] = head.val;
i++;
head = head.next;
}
//判断是否为回文
for(int j = 0;j<i/2;j++){
if(arr[j] != arr[i–1–j]){
return false;
}
}
return true;
}

解题思路：快慢指针+反转链表⭐

• 找链表中点：使用快慢指针，fast 走两步，slow 走一步，所以 fast 到末尾时，slow 正好到中间。

• 反转后半部分的内容（slow.next作为第一个需要进行处理的反转点）
• 比较两个链表

public boolean isPalindrome(ListNode head) {
//找到链表的中间点
ListNode slow = head,fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

//将链表的后半部分反转
ListNode prev = null;
ListNode cur = slow.next;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}

//判断是否为回文
while (prev != null) {
if (head.val != prev.val) {
return false;
}
head = head.next;
prev = prev.next;
}
return true;
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

4.环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

示例 2： 输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3： 输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

提示： 链表中节点的数目范围是 [0, 10^4] -10^5 <= Node.val <= 10^5 pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

解题思路：快慢指针

slow 每次走 1 步，fast 每次走 2 步。一旦都进入环里，fast 每一轮相对于 slow 都会多走一步。所以就相当于：slow 不动，fast 每轮靠近 slow 1 个节点。环长度有限，所以最终一定追上。

public boolean hasCycle(ListNode head) {
//快慢指针
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}

扩展：环形链表 II

环形链表 II

在题目的基础上增加对入环节点的输出

a = head 到入口的距离 b = 入口到第一次相遇点的距离 c = 相遇点继续走回入口的距离 L = b + c 为环的长度

快慢指针相遇时，慢针走过的节点长度为：slow = a + b + xL。 快慢指针走的距离相差两倍，即 fast = 2slow 同时快指针比慢指针多走了 n 圈 ，即 fast – slow = nL

=>可以得到 slow = nL = a + b + xL =>可以得到 a + b = kL => a + b 即为头节点 head 到相遇点的距离，kL 即为从相遇点开始走过的圈

public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
//找到环的入口
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}

扩展，输出入环节点，环的最后一个节点，环中包含几个节点

5.合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2： 输入：l1 = [], l2 = [] 输出：[]

示例 3： 输入：l1 = [], l2 = [0] 输出：[0]

提示： 两个链表的节点数目范围是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非递减顺序 排列

解题思路：双指针比较

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