东莞做网站的联系电,虚拟主机租赁,七台河建网站,软件资源网站对于单链表相关的问题#xff0c;双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决#xff1a; 合并两个有序链表#xff1a; 使用两个指针分别指向两个链表的头部#xff0c;逐一比较节点的值#xff0c;将较小的节点链接到结果链表… 对于单链表相关的问题双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决 合并两个有序链表 使用两个指针分别指向两个链表的头部逐一比较节点的值将较小的节点链接到结果链表中直至其中一个链表遍历完毕。 链表的分解 使用快慢指针技巧快指针每次移动两步慢指针每次移动一步直到快指针到达链表尾部。这样可以找到链表的中间节点从而将链表分解成两部分。 合并 k 个有序链表 可以利用归并排序的思想两两合并链表直到合并成一个链表。 寻找单链表的倒数第 k 个节点 使用两个指针让一个指针先移动 k 步然后两个指针一起移动直到第一个指针到达链表尾部此时第二个指针指向的节点即为倒数第 k 个节点。 寻找单链表的中点 同样使用快慢指针技巧快指针每次移动两步慢指针每次移动一步直到快指针到达链表尾部慢指针即为中点。 判断单链表是否包含环并找出环起点 使用快慢指针技巧如果存在环快指针最终会追上慢指针。找到相遇点后将其中一个指针移动到链表头部然后两个指针以相同速度移动再次相遇的节点即为环的起点。 判断两个单链表是否相交并找出交点 分别遍历两个链表得到它们的长度差然后让长链表的指针先移动长度差步数接着两个链表同时遍历直到找到相同的节点为止。 总的来说双指针技巧在解决单链表相关问题时非常实用它能够高效地解决许多常见问题包括合并、分解、寻找节点、判断是否存在环等等。而我们需要使用双指针解决的以上问题则是先要学会以下问题的解题思路一起看看。 一、相交链表
题目描述 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表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
输出null
解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。
由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。
这两个链表不相交因此返回 null 。提示
listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB] 解题思路及代码 可以让tempA的最后指向headBtempB的最后指向headA这样两指针虽然不相等但是两指针可以通过相同的速度移动相同的距离从而得到公共部分
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//判断是否为空if(headAnull || headBnull){return null;}ListNode tempAheadA;ListNode tempBheadB;//可以让tempA的最后指向headBtempB的最后指向headA这样两指针虽然不相等但是两指针可以通过相同的速度移动相同的距离从而得到公共部分while(tempA!tempB){tempAtempA.next;tempBtempB.next;if(tempAnull tempBnull)return null;if(tempAnull){tempAheadB;}if(tempBnull){tempBheadA;}}return tempA;}
}
结果展示 二、删除链表的倒数第k个节点
题目描述
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
示例 1 输入head [1,2,3,4,5], n 2
输出[1,2,3,5]示例 2
输入head [1], n 1
输出[]示例 3
输入head [1,2], n 1
输出[1]提示
链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 解题思路及代码 找第倒数n个节点。让快指针先走k步然后使用慢指针从头开始跟快指针按同样的速度行走等快指针走到结尾慢指针的节点就是倒是第k1个节点。
/*** 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 removeNthFromEnd(ListNode head, int n) {//哨兵ListNode tempnew ListNode(-1);temp.nexthead;ListNode resultfindNode(temp,n1);删除倒数第k个节点result.nextresult.next.next;return temp.next;}//找第倒数n个节点。让快指针先走k步然后使用慢指针从头开始跟快指针按同样的速度行走等快指针走到结尾慢指针的节点就是倒是第k1个节点。public ListNode findNode(ListNode head,int n){ListNode slowhead,fasthead;for(int i0;in;i){fastfast.next;}while(slow!null fast!null){slowslow.next;fastfast.next;}return slow;}
} 结果展示
