链表中双指针的技巧_链表双指针方法

链表中双指针的技巧

注:题目来源均来自力扣

文章目录

一:环形链表:(用于判断该链表是否为环形链表)

二:环形链表:(找出链表尾连接到链表中的位置)

三:相交链表:

四:删除链表的倒数第N个节点:

一:环形链表:(用于判断该链表是否为环形链表)

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

输入:head = [3,2,0,-4]，pos = 1

输出:true

输入:head = [1], pos = -1

输出:false

代码演示(仅展示功能函数，链表的创建应该都会)`

bool hasCycle(struct ListNode *head) {

if(head==NULL){

return false;//如果该链表为空链表，则该链表一定不为环形

}

struct ListNode*end;

end = head;

struct ListNode*new;

new=head;//定义两个指针

while(new!=NULL&&new->next!=NULL){

end=end->next;//第一个指针每次走1步

new=new->next->next;//第二个指针每次走两步

if(new==end){

return true;//如果快指针与慢指针相遇，则证明为环形

break;

}

}

return false;//若快指针与慢指针不相遇则证明不为环形

}

二:环形链表(找出链表尾连接到链表中的位置)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

输入：head = [1,2], pos = 0
输出：返回索引为 0 
解释：链表中有一个环，其尾部连接到第一个节点。
1
2
3

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
1
2
3

代码演示:

struct ListNode *detectCycle(struct ListNode *head) {

if(head==NULL){

return NULL;

}//若该链表为空，则必定不为环形

struct ListNode*end;

end=head;

struct ListNode*new;

new=head;//定义两个指针

while(new!=NULL&&new->next!=NULL){

end=end->next;//慢指针每次向后移动一位

new=new->next->next;//快指针每次向后移动两位

if(end==new){

break;

}

}

if(new==NULL||new->next==NULL){

return NULL;//若不为环形链表，则返回NULL

}

struct ListNode*new1;//定义新的指针

new1=head;

while(new1!=new){

new=new->next;

new1=new1->next;

}

return new1;//当新的指针与旧的指针相遇，返回

}

注意:

此题与上题相比较难,不妨画图

不妨令开始到入环的距离为D，当慢指针运动S1时与快指针相遇，环的长度为S1+S2

定义一个快指针与一个慢指针，快指针每次运动2步，慢指针每次运动一步，由图可知，慢指针运动了D+S1，快指针运动了D+n(S2+S1)+S1 (n为运动的圈数)

因为是相同的时间，所以快指针运动的距离是慢指针的2倍，可知 D+S1+(S1+S2)*n=2(D+S1)

化简可得D=(n-1)(s1+s2)+s2

而此时n=1,即D=s2

便可以新定义一个指针，让它从头开始运动，当它与慢指针相遇时，即可知道其位置

三:相交链表

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

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

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

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

自定义评测：

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

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

listA - 第一个链表

listB - 第二个链表

skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

输入：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 个节点。

代码演示

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

if(headA==NULL||headB==NULL){

return NULL;//如果链表为空

}

struct ListNode*new1;

new1 = headA;

struct ListNode*new2;

new2 = headB;

while(new1!=new2){

new1=(new1==NULL)?headB:new1->next;//如果new1为空，new1为headB否则new1取下一个

new2=(new2==NULL)?headA:new2->next;//如果new2为空, new2为headA否则new2取下一个

}

return new1;

}

这个方法不需要比较第一个链表与第二个链表哪个链表长哪个链表短

四:删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

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

代码演示

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* struct ListNode *next;

* };

*/

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){

struct ListNode*new1;

struct ListNode*new2;

new1=head;

new2=head;

for(int i=1;i<=n;i++){

new1=new1->next;//让快指针先运动n步

}

if(new1==NULL){

return head->next;//如果new1为空,删除的头结点

}

while(new1->next!=NULL){

new1=new1->next;

new2=new2->next;

}//当快指针为空时,慢指针的下一步就为要删除的节点

new2->next=new2->next->next;

return head;

}

注意:用双指针解决该题，核心思路是让快指针先走多少步，再让慢指针追赶它