【数据结构篇】~链表算法题3（环形链表）

环形链表的证明

1. 环形链表I​

https://leetcode.cn/problems/linked-list-cycle/description/

1) 思路

判断链表是否带环，还是要使用快慢双指针，如果带环那他们一定在环中相遇，如果没带环那么就返回false

2）代码实现

typedef struct ListNode ls;
bool hasCycle(struct ListNode *head) {ls*slow=head,*fast=head;//开始循环while(fast && fast->next)//分为奇数偶数两种情况所以要fast&&fast->next{slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;   
}

2. 环形链表II​

https://leetcode.cn/problems/linked-list-cycle-ii/description/​

1) 思路1

找到相遇节点，然后把相遇节点的next指针置为newnode，再把meet->next置为空，这时再找入环节点就可以转化为找相交链表的相交节点

1) 思路2

找到相遇节点后然后开时循环，让相遇节点和头节点同时同步走，直到两个指针相遇时，就找到了入环节点

2）代码实现

typedef struct ListNode lsnode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{lsnode*l1=headA;lsnode*l2=headB;int sizea=0;int sizeb=0;while(l1){++sizea;l1=l1->next;      }while(l2){++sizeb;l2=l2->next;     }//计算a和b的长度，让长的先走差值步，到同一起点上lsnode* plong = headA;lsnode* pshort = headB;if(sizeb>sizea){plong= headB;pshort=headA;}int gap=abs(sizea-sizeb);while(gap--){plong = plong -> next;}//开始比较while(plong && pshort){//这里比较地址，如果比较值得话有问题if(plong == pshort){ return pshort;}//同步走plong=plong->next;pshort=pshort->next;    }return NULL;   
}
struct ListNode *detectCycle(struct ListNode *head) 
{lsnode*slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){lsnode*meet=slow;//相遇节点lsnode*newhead=meet->next;meet->next=NULL;//变为了相交链表找相交节点return getIntersectionNode(head,newhead);}       }  return NULL;
}```c
typedef struct ListNode  lsnode;
struct ListNode *detectCycle(struct ListNode *head) 
{lsnode*slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){lsnode*meet=slow;//相遇节点while(head!=meet){head=head->next;meet=meet->next;}return meet;}      }  return NULL;   
}