[C topic] force buckle 876. Intermediate node of linked list

876. The middle node of a list - Power button （LeetCode）

  Method 1 ： Calculate the number of nodes count, Move count/2 The second is the node required by the topic . 

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* cur=head;// Mark the current node 
    int count=0;//count Record the number of nodes 
    while(cur)// Calculate the number of nodes 
    {
        count++;
        cur=cur->next;
    }
    cur=head;// Back to the head node 
    for(int i=0;i<(count/2);i++)// The first cycle ,cur For the first time 2 Nodes . The first (count/2)+1 Nodes , Need to cycle count/2 Time .
    {
        cur=cur->next;
    }
    return cur;
}

Method 2 ： Speed pointer .slow and fast The starting points are head,slow Move backward one node at a time ,fast Move back two nodes at a time .fast Moving two nodes backward is called fast->next->next assignment , This premise is fast->next Not for NULL, and fast->next Not for NULL The premise is fast Not for NULL. Therefore, the cycle judgment condition is (fast&&fast->next), also fast Must be written in fast->next Left side , When the number of nodes is even ,slow After reaching the intermediate node ,fast by NULL, Because logical operators && Will control the evaluation order , They don't execute fast->next, perform fast->next Will dereference null pointers .

（ The picture shows that , When the number of nodes is odd ,slow After reaching the intermediate node fast->next by NULL, End cycle . When the number of nodes is even ,slow After reaching the intermediate node fast by NULL, End cycle . Find the intermediate node and return .）

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}