2, 使用反转指针的方法, 每过一个节点就把该节点的指针反向:
Boolean reverse(Node *head) {
Node *curr = head
Node *next = head->next
curr->next = NULL
while(next!=NULL) {
if(next == head) { /* go back to the head of the list, so there is a loop */
next->next = curr
return TRUE
}
Node *temp = curr
curr = next
next = next->next
curr->next = temp
}
/* at the end of list, so there is no loop, let's reverse the list back */
next = curr->next
curr ->next = NULL
while(next!=NULL) {
Node *temp = curr
curr = next
next = next->next
curr->next = temp
}
return FALSE
}
看上去这是一种奇怪的方法: 当有环的时候反转next指针会最终走到链表头部当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候).
这个方法的最大缺点是在多线程情况下不安全, 当多个线程都在读这个链表的时候, 检查环的线程会改变链表的状态, 虽然最后我们恢复了链表本身的结构, 但是不能保证其他线程能得到正确的结果.
3, 这是一般面试官所预期的答案: 快指针和慢指针
Boolean has_loop(Node *head) {
Node *pf = head/* fast pointer */
Node *ps = head/* slow pointer */
while(true) {
if(pf &&pf->next)
pf = pf->next->next
else
return FALSE
ps = ps->next
if(ps == pf)
return TRUE
}
}
需要说明的是, 当慢指针(ps)进入环之后, 最多会走n-1步就能和快指针(pf)相遇, 其中n是环的长度. 也就是说快指针在环能不会跳过慢指针, 这个性质可以简单的用归纳法来证明. (1)当ps在环中位置i, 而pf在环中位置i-1, 则在下一个iteration, ps会和pf在i+1相遇.
(2)当ps在环中位置i, 而pf在环中位置i-2, 则在下一个iteration, ps在i+1, pf在i, 于是在下一个iteration ps和pf会相遇在i+2位置
(3)和上面推理过程类似, 当ps在i, pf在i+1, 则他们会经过n-1个iteration在i+n-1的位置相遇. 于是慢指针的步数不会超过n-1.
扩展:
这个问题还有一些扩展, 例如, 如何找到环的开始节点? 如何解开这个环? 这些问题的本质就是如何找到有"回边"的那个节点.
我们可以利用方法3的一个变形来解决这个问题:
Boolean has_loop(Node *head) {
Node *pf = head/* fast pointer */
Node *ps = head/* slow pointer */
while(true) { /* step 1, is there a loop? */
if(pf &&pf->next)
pf = pf->next->next
else
return FALSE
ps = ps->next
if(ps == pf)
break
}
/* step 2, how long is the loop */
int i = 0
do {
ps = ps->next
pf = pf->next->next
i++
} while(ps!=pf)
/* step 3, use 2 addtional pointers with distance i to break the loop */
ps = head
pf = head
int j
for(j=0j<ij++) { pf = pf->next}
j = 0
while(ps!=pf) {
ps = ps->next
pf = pf->next
j++
}
printf("loop begins at position %d, node address is %x", j, ps)
/*step 4, break the loop*/
for(j=0j<=ij++) { ps = ps->next} //step i-1 in the loop from loop beginning
ps->next = NULL// break the loop
return TRUE
2021-11-10
列表是一种非连续的存储容器，有多个节点组成，节点通过一些变量记录彼此之间的关系
单链表和双链表就是列表的两种方法。
原理：A、B、C三个人，B懂A的电话，C懂B的电话只是单方知道号码，这样就形成了一个单链表结构。
如果C把自己的号码给B，B把自己的号码给A，因为是双方都知道对方的号码，这样就形成了一个双链表结构
如果B换号码了，他需要通知AC，把自己的号码删了，这个过程就是列表的删除操作。
在Go语言中，列表使用 container/list 包来实现，内部的实现原理是双链表，列表能够高效地进行任意位置的元素插入和删除操作。
列表初始化的两种办法
列表没有给出具体的元素类型的限制，所以列表的元素可以是任意类型的，
例如给列表中放入了一个 interface{} 类型的值，取出值后，如果要将 interface{} 转换为其他类型将会发生宕机。
双链表支持从队列前方或后方插入元素，分别对应的方法是 PushFront 和 PushBack。
列表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除。
遍历完也能看到最后的结果
学习地址： http://c.biancheng.net/view/35.html
![Golang nethttp 爬虫[1]](/aiimages/Golang+nethttp+%E7%88%AC%E8%99%AB%5B1%5D.png)
