【数据结构篇】~链表算法题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;   
}

3. 随机链表的复制​

https://leetcode.cn/problems/copy-list-with-random-pointer/description/​

1) 思路

深拷贝就是把所有数据都复制下来，创建节点malloc，放置当前节点的next，当前节点再往后走2个next，然后再创建复制节点

2）代码实现

typedef struct Node node;
node* buynode(int val)//申请新节点
{node* newnode = (node*)malloc(sizeof(node));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->val = val;newnode->next = newnode->random = NULL;return newnode;
}
struct Node* copyRandomList(struct Node* head)
{if(head==NULL) return NULL; node* phead1 = head;//复制节点用node* phead2 = head;//尾插用node* phead3 = head;//置random用while (phead1)//开始复制节点{node* newnode = buynode(phead1->val);newnode->next = phead1->next;phead1->next = newnode;phead1 = newnode->next;}//置random要和复制链表分开while(phead3){node* newnode1=phead3->next;if(phead3->random != NULL){newnode1->random = phead3->random->next;}phead3=newnode1->next;}//这里是尾插node* newhead,* newtail;newhead = newtail = phead2->next;//第一个复制的节点while (phead2->next->next){phead2 = phead2->next->next;newtail->next = phead2->next;newtail = newtail->next;			}return newhead;	
}
``