（1.2.1.1）单链表的逆转倒置、验环、倒数第M个节点和相交

发布时间：2020-12-13 22:34:33 所属栏目：百科来源：网络整理

导读：（1）反向逆置 //逆置单向链表 //通过三个指针遍历 O（n） LNode*ListInverse(LNode*L) { if (L==NULL) return NULL; if (L-Next==NULL) return L; LNode*pre=L-Next; LNode*cur=pre-Next; LNode*next=cur-Next; pre-Next=NULL; cur-Next=pre; pre=cur; cur=

（1）反向逆置

//逆置单向链表
//通过三个指针遍历 O（n）
LNode*ListInverse(LNode*L)
{
if(L==NULL)
returnNULL;
if(L->Next==NULL)returnL;
LNode*pre=L->Next;
LNode*cur=pre->Next;
LNode*next=cur->Next;
pre->Next=NULL;
cur->Next=pre;
pre=cur;
cur=next;
while(cur!=NULL)
next=cur->Next;
}
L->Next=pre;
}

[html] view plain copy

//头插法遍历

copy

publicvoidReversLinkList(LinkList<int>H)
{

Node>p=H.Next;

Node>q=newNode>();

H.Next=null;

while(p!=null)

{

q=p;

p=p.Next;

q.Next=H.Next;

H.Next=q;

}

（2）验证环

正常链表的尾节点的链域是NULL，有环就不存在NULL了！对了，用一指针轮询，不断地p=p->next;若是看到了p为NULL，则表明无环！否则，就是有环。这个想法挺好，但是有环，会进入死循环的。有

办法是有的：使用两指针，一快一慢，都从头开始轮询，若有环，则慢的肯定可以被快的反超，因为此时大家都像是在围绕着环形跑道赛跑；若是一正常链表，则肯定会遇到NULL，好了，问题解决了。

[cpp] view plain copy

boolhasLoop(Node*head)
{
if(head==NULL)//链表为空
returnfalse;
Node*p,*q;
p=q=head;//两个指针从同一点出发，当然也可以一前一后
while(p&&q)
p=p->next;//一次一步
q=q->next->next;//一次两步
if(p==q)//相遇，肯定有环
true;
}
false;//出现了NULL，也就无环
}

（3）倒数第M个节点

两指针，一指针先从头移动k次，此时两指针间隔k(就是要这个差距)，此时两指针同时移动，快慢一样，等到先走的指针移动到NULL，第二个指针不就是倒数第k个

endOfK(Node*head,

int

if(head==NULL)
printf("链表为空！");
return;
Node*p,*q;
p=q=head;
intcount=0;
while(p&&count<k)
p=p->next;
count++;
if(p==NULL&&count!=k)//update:这里原先只有p==NULL，更新后加上count!=k，大家想想为什么？
{
printf("k值过大！n");
return;
}
while(p)
q=q->next;
printf("倒数第%d个节点是%dn",k,q->data);
}

（4）相交

一指针沿着其中一链表走到尾节点处等着，另一链表的指针也从头走到尾，若能在尾处相遇，则两链表在某节点处相交。

寻找相交节点

不妨遍历每个链表保存最后一个节点，看看最后一个节点是否是同一个节点，这种情况时间复杂度是O（length1 + length2）。基本也不需要什么空间，似乎是一个不错的想法哦，那么怎么找到第一个相交节点呢？可以遍历的过程中记录链表的长度L1和L2(假设L1>L2)这是遍历找到第一个链表中的第L1 - L2节点，然后链表一从第L1-L2个节点开始遍历，链表二从第一个节点遍历，每次前进一步，直到找到第一个相同的节点，则可以认为两个链表存在相交节点，并且该点即为第一个相交节点（原来这里写错了，感谢Ider指出这个错误）。这种解法的时间复杂度也是线性的，但是如果两个链表长度相差不多时，时间复杂度还是不错的。

（10）寻找环的入口点

1. 遍历链表，将已经遍历过的节点放在一个hash表中，如果一个节点已经存在hash表中，说明有环。时间:O(n) 空间:O(n)

2.寻找环的入口点：当fast按照每次2步，slow每次一步的方式走，发现fast和slow重合，确定了单向链表有环路。接下来，让fast回到链表的头部，重新走，每次步长1，那么当fast和slow再次相遇的时候，就是环路的入口了。

证明：在fast和slow第一次相遇的时候，假定slow走了n步，环路的入口是在p步，那么

slow走的路径： p+c ＝ n； c为fast和slow相交点距离环路入口的距离

fast走的路径： p+c+k*L = 2*n； L为环路的周长，k是整数

显然，如果从p+c点开始，slow再走n步的话，还可以回到p+c这个点。

同时，fast从头开始走，步长为1，经过n步，也会达到p+c这点。

显然，在这个过程中fast和slow只有前p步骤走的路径不同。所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

（编辑：李大同）