链表浅析

[bosthhe1]

链表是值在空间结构上不连续，但是在逻辑结构上连续的，链表一般是为一个结构体指针，结构体指针里面包含两个元素，第一个元素为值，第二个元素为地址，第二个元素的地址，指向的下一个结构体指针，这样下去，直到最后一个指针的第二个地址指向空，为链表结束。 1，链表的翻转; struct SListBack(struct SListBack SlistNode) {//struct SListBack cur = SlisNode;//第一个元素 struct SListBack Next = SlisNode->next;//将先将第二个元素的地址保存起来 struct SListBack* Ahead = SlisNode; Ahead->next = NULL;//先将第一个指针指向地址制空 while(cur->next)//循环,最后一个元素没有链接 { cur = Next;//cur为下一个元素的地址 cur->next=Ahead;//将cur的next链接到Ahead Ahead = cur;//将Ahead移到下一个元素的地址 Next = Next -> next;//将Next移到下一个元素的地址 } cur ->next = Ahead; return cur; }

[bosthhe1]

2,分支链表回文（思路和链表翻转一样） struct SListBack(struct SListBack SlistNode) {//struct SListBack cur = SlisNode;//第一个元素 struct SListBack Next = SlisNode->next;//将先将第二个元素的地址保存起来 struct SListBack* pre =NULL;

while(cur)//循环,最后一个元素没有链接 { cur->next = pre; pre = cur; cur =Next; if(Next) {Next=Next >next} } return cur; }

[bosthhe1]

3，判断链表是否存在环(快慢指针) 存在环返回Ture不存在返回NULL； struct SListBack(struct SListBack SlistNode) {//struct SListBack Slow = SlisNode->next;//第一个元素 struct SListBack Fast = SlisNode->next->next;//速度为slow的两倍 while(Fast) { if(Fast ==Slow) { return Ture; } Fast = Fast ->next ->next; slow = slow ->next; } return NULL; }

[bosthhe1]

快慢指针的衍生 对于快慢指针，如果规定Fast的速度为Slow的2倍；那么一定会相遇

对于快慢指针，如果规定Fast的速度为Slow的3倍；不一定会相遇 若c-1为2的倍数，则会相遇

对于快慢指针，如果规定Fast的速度为Slow的4倍；不一定会相遇 若c-1为3的倍数，则相遇

[bosthhe1]

对快慢指针的衍生。若存在环，则找出环的起点 方法一； 已知Slow和Fast在环中相遇，相遇点为newnode，然后将newnode点，一分为二，则变为指针相交的问题 struct SListBack(struct SListBack SlistNode) {struct SListBack Slow = SlisNode;->next//第一个元素 struct SListBack Fast = SlisNode->next->next;//走两步，指向第二个元素 struct SListBack Ahead = SlisNode;//保存头 struct SListBack AAhead = NULL;//用于保存相遇时newnode剪开的地址。 while(Fast)//Fast比 Slow快，若Fast为NULL了，则不为环 { if(Fast ==Slow) { AAhead=Slow->next;//新的头，这个头指向Slow（因为是个循环） Slow ->next=NULL;//断开制空，作为结尾。 break; } Fast = Fast ->next->next;//如果不是相遇点，继续走 Slow = Slow ->next; } while(Ahead->next !=NULL)//时间复杂度为N(O^2)(笨方法) {

while(AAhead->next !=NULL) { if(Ahead->next==AAhead->next) { return Ahead->next;//找到了环的起始节点，返回去。 } AAhead = AAhead ->next; } Ahead = Ahead ->next;//走到这，说明第一个节点不为环节点的首节点，然后开始判断下一个点。 } }

[bosthhe1]

对快慢指针的衍生。若存在环，则找出环的起点 方法二；需要借助图来理解 struct SListBack(struct SListBack SlistNode) {struct SListBack Slow = SlisNode;->next//第一个元素 struct SListBack Fast = SlisNode->next->next;//走两步，指向第二个元素，Fast速度为Slow的两倍 struct SListBack Ahead = SlisNode;//保存头 struct SListBack newnode = SlisNode;//保存相遇点 while(Fast)//Fast比 Slow快，若Fast为NULL了，则不为环 { if(Fast ==Slow)//相遇点 { newnode =Slow->next;//保存相遇点 break; } Fast = Fast ->next->next;//如果不是相遇点，继续走 Slow = Slow ->next; } while(Ahead) { newnode = nownode ->next; Ahead = Ahead ->next; if(newnode->next == Ahead ->next)//找环的头节点 { return Ahead ->next; } }

[bosthhe1]

相交问题 方法一；（笨方法）时间复杂度O(N^2); 已知Slow和Fast在环中相遇，相遇点为newnode，然后将newnode点，一分为二，则变为指针相交的问题 struct SListBack(struct SListBack SlistNode) {struct SListBack Ahead = SlisNode;//一个结构体指针 struct SListBack AAhead = SlisNode;//另一个结构体指针 while(Ahead->next !=NULL)//时间复杂度为N(O^2)(笨方法) { while(AAhead->next !=NULL) { if(Ahead->next==AAhead->next) { return Ahead->next;//找到了环相交点 } AAhead = AAhead ->next; } Ahead = Ahead ->next;//进入下一个循环 } return NULL;//没有相交 }

[bosthhe1]

相交问题 方法二算出每个链条走到结尾并计算长度，如果结尾不等，则不相等，若相等，则计算出两个链条的长度差，时间复杂度O(N) struct SListBack(struct SListBack SlistNode , struct SListBack SSlistNode) {struct SListBack Ahead = SlisNode;//一个结构体指针 struct SListBack* AAhead =SSlisNode;//另一个结构体指针 int count ,num; while(Ahead->next!=NULL) { Ahead = Ahead->next; count++; } while(AAhead->next!=NULL) { AAhead = AAhead->next; num++; } Ahead = SlisNode;//先将Ahead指回开头； AAhead = SSlisNode;//先将AAhead指回开头； int x = (count>num)?count,num; if(x == count) { while(--count) { Ahead = Ahead ->next; } while(Ahead->next!=NULL) { if(Ahead->next==AAhead->next) { return Ahead->next; } Ahead=Ahead->next; AAhead=Ahead->next; } } if(x == num) { while(--num) { AAhead = AAhead ->next; } while(AAhead->next!=NULL) { if(Ahead->next==AAhead->next) { return AAhead->next; } Ahead=Ahead->next; AAhead=Ahead->next; } }