泸州市建设工程质量监督站网站,广告投放方式,网站 科技感,域名注册流程及费用1. 力扣876#xff1a;链表的中间节点
1.1 题目#xff1a;
给你单链表的头结点 head #xff0c;请你找出并返回链表的中间结点。
如果有两个中间结点#xff0c;则返回第二个中间结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[3,4,…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;}
}
