算法学习（六）链表问题总结，相交，成环算法学习

求链表倒数第K个结点
题目描述：
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第0个结点为链表的尾指针。
分析：
首先链表是一个顺序结构，不像数组寻址比较方便，链表一般都是通过遍历来寻址，所以碰到倒数这种情况，转化为求L-K个结点，L为链表长度，所以你需要先遍历，得到链表的长度，然后再遍历找到第L-K个结点。这样是不是有点low啊，是的，下面就是经典的双指针方法，这里要再次强调下链表的一个特性，特指单向链表，最后一个结点Lastnode ->next = NULL，这个是链表使用的关键点，可以作为一个标志位，作为循环结束的标志。p1 指向头指针，p2指向和p1相隔K的结点，然后两个指针一起向后移，直到p2到达链表尾部，这时候，p1的结点就是倒数第k个结点。

//代码中顺便写了链表的增删查功能 #include.h> #include typedef struct Node * Position; typedef Position List; struct Node { int value; Position next; }; void Insert(Position P,List L,int x)//List L 表示头指针 { Position temp; temp = (Node *)malloc(sizeof(struct Node)); temp->value = https://www.it610.com/article/x; temp->next = P->next; P->next = temp; } Position Find(List L,int x) { Position start; start = L->next; while(start != NULL && start->value != x) start = start->next; return start; } int IsEmpty(List L) { return L->next == NULL; } void Delete(List L,int x) { Position P,temp; P = L; while(P->next != NULL && P->next->value != x) P= P->next; if(P->next != NULL) { temp = P->next; P->next = temp->next; free(temp); } } //查找倒数第K个结点 Position FindListBackNode(List L ,int k) { Position P1,P2; assert(k>=0); P1 = P2 = L; int i; for(i = k; i> 0 && P2 != NULL ; i--)//使p2和p1相隔k个结点 { P2 = P2->next; } if(k > 0) return NULL; while(P2 != NULL) { P1 = P1->next; P2 = P2->next; } return P1; }

判断两个链表是否相交
题目描述：给出两个单向链表L1，L2 ,判断两个链表是否相交，假设两个链表都无环。
分析：
相交意思就是是否存在结点相同，遍历链表L1的每个结点，判断是否在第二个链表中，时间复杂度为O (length（L1） * length（L2）)。
你会发现这个就是个查找问题，查找最快的当然是hashtable,先遍历链表L1,构造hash表，然后遍历链表L2，判断L2结点是否能再hash表中找到，时间复杂度为O（length(L1) + length(L2)）,不过空间复杂度为O（length(L1)）。
如果两个无环链表有交点，那么这个交点之后的所有结点都相同，当然最后的结点也一定是共有的，so,我们直接判断最后一个结点时候相等就好了，先遍历链表L1，找到尾结点，再遍历遍历L2,找到尾结点，然后比较，相同就相交，时间复杂度为O（length(L1) + length(L2)）,空间复杂度为O（1）。
那么问题来了，如果链表有环呢？
有环的话，上面的判断尾结点方法就行不通了，
如果一个带环一个不带环呢，当然肯定不相交了。
所有问题就转化为先判断是否有环？
链表是否有环？

文章图片

用画图画的，凑合着看吧，这个就是带环的链表，首先要区分循环链表和带环链表的区别。循环链表就是首尾相连，相当于一个圆，带环链表意思是没有结尾，不会指向NULL ,感觉循环链表应该是有环链表的一种特殊情况，此处我们去掉循环链表这种特殊情况，判断链表是否有环，可以联想到以前数学中的追赶问题，两个人从相同起点出发，一个速度快，一个速度慢，经过一段时间，速度快的从追上速度慢的人，比速度慢的人多跑了一圈，这个逻辑可以用在判断链表是否有环，一个指针P1每次移动一步，一个指针p2移动两步，如果这个两个指针相等（而且不等于null）,意思就是p2绕了n圈之后再次追上p1。

bool isCircle(List L,Positon lastnode,Position circleNode) { Position fast= L->next; //快的要先出发 Position slow = L; while(fast != slow && fast != NULL && slow != NULL) { if(fast->next != NULL) fast = fast->next; //快的比慢的多走一步 if(fast->next == NULL) lastnode = fast; //最后的尾结点 if(slow->next == NULL) lastnode = slow; fast = fast->next; slow = slow->next; } if(fast == slow && fast != NULL && slow != NULL) { circleNode = fast; //两个快慢指针第一次相遇的地点，肯定在环上。 return true; } else return false; }

再次回到判断链表是否有交点上，
先判断是否有环，
如果无环，判断尾结点是否相等，
如果有环，遍历L1环上的每个结点是否和L2环上某个结点相等

bool detect(List L1,List L2) { Position circleNode1; //环上的结点 Position lastNode1 ; Position circleNode2; Position lastNode2; bool iscircle1 = isCircle(L1,circleNode1,lastNode1); bool iscircle2 = isCircle(L2,circleNode2,lastNode2); if(iscircle1 != iscircle2) return false; else if(!iscircle1 && !iscircle2) return lastNode1 == lastNode2; else { Position temp = circleNode1->next; while(temp != circleNode1) { if(temp == circleNode2) return true; temp = temp->next; } return false; } return false; }

链表成环，环的入口在哪？

文章图片

又来秀画图了，viso懒得用，电脑打开都费劲
下面是数学时间：
链表的总长度为L，链表起点为A，环入口为B，第一次相遇的点为C(就是上面那个快慢指针相遇的点)，A到B 的长度为a,B到C的长度为x，环一圈的长度为r。
fast 和slow指针相遇的时候，slow肯定没有遍历完链表，fast此时已经在环里转了n圈，此时slow走了s步，那么fast已经走了2s步（是慢的两倍），所以可以建立表达式：
s+nr = 2s
s = nr
因a+x = s， r = L-a
所以 a+x = nr
a+x = (n-1)r+r = (n-1)r +L-a
a = (n-1)r + L-a-x
(L-a-x)是C 到B的距离，相遇点到环入口的距离
可以知道，从链表头到环入口等于（n-1）循环内环+相遇点到环入口，
所以P1从链表头出发，而P2从相遇点出发，当两者再次相遇时的结点就是环入口。
【算法学习（六）链表问题总结，相交，成环】待续，后续会继续添加