[数据结构与算法]链表的基础和一些提升

如果你是萌新的话，建议先去把c语言书上的指针和结构体先去学，不然会听不明白，书上的东西讲得很详细。

struct student{
    long num;
    float score;
    struct student*next;
};
//定义一个结构体，同时定义一个结构体指针指向第下一个结构体，完成连接。

链表要有head（头）指针！！！！

struct student *head;
struct student *p1,p2;
head=NULL;//将头指针变成空指针

剩下的一些基础建议自己去看书，书上讲得比我好-----。

后面内容是书上没有的，感兴趣的可以看看！

1、环形链表

你需要判断你的链表中是否有环形链表。

仔细思考！

你可以想想龟兔赛怕，如果赛道是环形的，那么兔子和乌龟一定可以相遇，否则就无法相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        struct ListNode*fast=head;
        struct ListNode*slow=head;//用2个指针分别表示兔子和乌龟
        while(fast&&fast->next)//这个意思是fast指针不是空，fast后面的也不为空
        {
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast)break;//相遇则退出循环
        }
        if (fast==NULL||fast->next==NULL)//判断是否有环
        return NULL;
        //有环由上可以推出快比慢多走了环长的1倍
        //这个时候，继续前进到入环口的距离 与 起点走到入环口的距离恰好相等
        fast=head;
        while(fast!=slow)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }
};

这是双指针的应用，可以去找一些题目练手。

// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow && fast && fast->next) {
    slow = slow->next;          // move slow pointer one step each time
    fast = fast->next->next;    // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem
这个是模板，快慢指针！！！！