leetcode-链表经典题

1.反转单链表

1. 反转链表https://leetcode.cn/problems/reverse-linked-list/这里我们使用创建一个变量cur来遍历原链表，再创建一个新节点newnode，首先使用一个循环来遍历原链表，cur为NULL是循环结束，每次进入循环将cur的下一个节点赋给tail，然后将cur取下来头插，第一次头插的节点的next置为NULL，也就是cur->next=newnode,然后将cur这个节点赋给newnode，在新链表上相当于往左走一步，newnode=cur,然后cur在旧链表上往右走，cur=tail。循环结束后cur就为NULL了，也就是全部完成头插了，这是newnode也走到了新链表最左边的位置，也就是成为了头节点，这时返回newnode就行了。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newhead=NULL;
    while(cur)
    {
        struct ListNode* tail=cur->next;
        //头插
        cur->next=newhead;
        newhead=cur;
        cur=tail;
    }
    return newhead;
}

2.移除链表元素

移除链表元素https://leetcode.cn/problems/remove-linked-list-elements/首先创建一个变量newnode，用来保存新链表的头节点，再创建一个变量tail，由于新链表的尾插，再创建一个变量cur遍历原链表。

这里我们要考虑很多种情况：

1.链表为NULL，直接返回NULL。

2.如果cur->val==val,创建一个指针del保存cur，然后cur走到下一个节点，free掉del，这就是删除步骤。

3.如果cur->val!=val,进行尾插，这里也分两种情况，第一种就是新链表为空，则tail=cur=newnode。第二种就是不为空，正常尾插，先将tail->next=cur,然后tail往后走，tail=tail->next，在第三种情况里面无论走哪一步cur都要往后走一步，cur=cur->next。

循环结束之后cur就遍历完了，这时还要做的一个小细节就是判断一下tail是否为NULL，如果为NULL，就将tail->next置空即可。

返回newnode即可。

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode* newhead=NULL,*tail=NULL,*cur=head;
    while(cur)
    {
        if(cur->val==val)//删除
        {
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
        else//尾插
        {
            if(tail==NULL)
            {
                newhead=tail=cur;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
            cur=cur->next;
        }
    }
    if(tail)
    tail->next=NULL;
    return newhead;
}

3.求链表的中间节点

1. 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/这里就需要用到快慢指针来找中间节点，首先创建两个指针，分别为slow和fast，使用一个循环遍历链表，结束条件就是fast和fast->next其中一个为空，然后fast每次走两步，slow每次走一步，当fast走到最后一个节点，slow就是中间节点，如果链表有偶数个节点，不用担心，假设这个链表有6个节点，fast每次走两步会走到NULL这个位置，用了三次，slow走三次就走到了第四个节点，所以是刚好的。

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

今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。