当前位置：首页 > news >正文

【数据结构与算法 | 灵神题单 | 快慢指针(链表)篇】力扣876, 2095， 234

news 来源：原创 2024/9/20 0:26:05

1. 力扣876：链表的中间节点

1.1 题目：

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

1.2 思考

快慢指针轻松解决。快指针每次走2步，慢指针每次走一步，快指针走完，慢指针走完了1 / 2，只是最后返回的时候需要判断一下，链表的长度是奇数还是偶数而已。简单判断一下就好了。

1.3 题解：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode middleNode(ListNode head) {if(head == null) {return null;}ListNode fast = head;ListNode slow = head;while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}return fast.next == null ? slow : slow.next;}
}

2. 力扣2095：删除链表的中间节点

2.1 题目：

给你一个链表的头节点 head 。删除链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

提示：

链表中节点的数目在范围 [1, 105] 内
1 <= Node.val <= 105

2.2 思考

根据快慢指针的思想和两个案例，比较简单。

2.3 题解：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteMiddle(ListNode head) {if(head == null || head.next == null){return null;}// 头节点也可能被删除，所以需要哨兵节点ListNode dummy = new ListNode(10086, head);ListNode fast = dummy;ListNode slow = dummy;// 快指针和慢指针都从哨兵节点位置开始跑// 快指针每次走2步，慢指针每次走1步while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}// 分析两个测试，当fast停止步伐，slow都停在要删除节点的上一个节点slow.next = slow.next.next;return dummy.next;}
}

3. 力扣234：

3.1 题目：

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

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

3.2 思路1：

将判断回文链表的问题转换为判断回文数组的问题。时间复杂度O(n), 空间复杂度O(n)。

还可以使用快慢指针法解决这个问题。从头节点开始，快指针每次走2步，慢指针每次走一步。快指针走完时，慢指针走到中间节点的上一个节点，然后将链表分为两个部分，将后半部分反转链表，然后就可以从两个链表的头节点开始比较。不如回文数组方法一根。

3.3 题解1：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {// 用栈的前提是把链表的中间节点首先从栈里给踢掉public boolean isPalindrome(ListNode head) {if(head == null || head.next == null){return true;}int n = 0;ListNode p = head;while(p != null){n++;p = p.next;}int[] arr = new int[n];p = head;int i = 0;while(p != null){arr[i++] = p.val;p = p.next;}// n表示数组长度，下面要表示索引，所以-1n--;for(i = 0; i < arr.length / 2; i++){if(arr[i] != arr[n--]){return false;}}return true;}
}

4. 力扣2130：链表最大孪生和

4.1 题目：

在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。

比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

示例 3：

输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

提示：

链表的节点数目是 [2, 105] 中的偶数。
1 <= Node.val <= 105

4.2 思考1

跟上题思路一模一样，转化成求解数组的问题，直接秒。

4.3 题解1：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int pairSum(ListNode head) {// 将链表的问题转变为数组的问题int n = 0;ListNode p = head;while(p != null){n++;p = p.next;}p = head;int[] arr = new int[n];int i = 0;while(p != null){arr[i++] = p.val;p = p.next;}n--;// 因为链表节点的值都是正的，所以可以设置为0int max = 0;for(i = 0; i < arr.length / 2; i++){max = Integer.max(max, arr[i]+arr[n--]);}return max;}
}

4.4: 思考2：

快慢指针法解决，时间上来说跟上面的方法差不多，但从空间上有了很大的进步。借用了一个哨兵节点的空间。而上一种方法却是申请了链表长度的数组。

4.5 题解2：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public int pairSum(ListNode head) {// 快慢指针ListNode fast = head;ListNode slow = head;// 快指针一次走2步，慢指针一次走一步// 题目说了，链表的长度至少是2个// 所以就放心使用fast.next，不用担心fast空指针问题while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//此时slow节点指向了中间节点的前一个节点// 记录slow指针的下一个节点ListNode next = slow.next;// 将一个链表一分为2slow.next = null;slow = next;// 此时slow才指向链表的中间节点// 下一步就是反转链表slow = traverse(slow);// 记录最大孪生和int max = 0;while(head != null){max = Integer.max(max, head.val + slow.val);head = head.next;slow = slow.next;}return max;}// 该方法返回了一个新的头节点private ListNode traverse(ListNode head){// 新链表的哨兵节点ListNode dummy = new ListNode(10086, null);// 头插法while(head != null){ListNode p = head.next;head.next = dummy.next;dummy.next = head;head = p;}return dummy.next;}
}