【数据结构】单链表OJ题

🔥博客主页：小王又困了

📚系列专栏：数据结构

🌟人之为学，不日近则日退

❤️感谢大家点赞👍收藏⭐评论✍️

一、移除链表元素

💡方法一：

💡方法二：

二、链表的中间节点

💡方法一：

三、链表中倒数第k个结点

💡方法一：

四、反转链表

💡方法一：

💡方法二：

五、合并两个有序链表

💡方法一：

🗒️前言：

在上一期中我们给大家介绍了单链表，也了解了单链表的实现。接下来就让我们进入实践，练习一些经典题目，让我们对单链表的理解更加深入。

一、移除链表元素

题目：

💡方法一：

我们使用两个指针遍历数组，遇到与 val 相同的数据域，就删除这个节点。我们在思考问题时要想全面，当要删除头节点时，常规方法就无法实现，对于删除头节点要做单独处理。

🍩常规删除：

🍩头节点删除

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur!=NULL)
    {
        //删除
        if(val==cur->val)
        {
            //头删
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            //常规
            else
            {
                prev->next=cur->next;
                free(cur);
                cur=prev->next;
            }
        }

        //遍历
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

💡方法二：

我们通过遍历，把节点的数据域不等于val的节点尾接到新的链表中。我们要考虑第一个节点是不是要删除的。最后一个节点的指针域置空要放在循环结束后，判断tail是否为空指针。

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

二、链表的中间节点

题目：

💡方法一：

我们可以定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到结尾时，慢指针正好走了一半，这样我们就可以找到中间节点。
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head;
    struct ListNode* slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

三、链表中倒数第k个结点

题目：

💡方法一：

我们可以参考上一题的方法，同样定义快慢指针，想让快指针走k步，然后在同时走，走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点，所以我们要加入判断。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
       struct ListNode* fast=pListHead;
       struct ListNode* slow=pListHead;
        while(k--)
        {
            //链表没有k步长
            if(fast==NULL)
            {
                return NULL;
            }
            fast=fast->next;
        }
       while(fast!=NULL)
       {
            fast=fast->next;
            slow=slow->next;
       }
    return slow;
}

四、反转链表

题目：

💡方法一：

我们定义三个指针n1,n2,n3，来改变节点链接的顺序。将头节点变为尾节点，当n2为空指针时，n1就为链表的头节点，只需返回n1就可以。两个指针倒方向，一个指针保持下一个。
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3;
    if(n2)
    {
        n3=n2->next;
    }
    while(n2)
    {
        n2->next=n1;
        
        //往后走
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

💡方法二：

将链表的节点一个一个拿下来，进行头插。这里要注意赋值的顺序。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newnode=NULL;
    while(cur)
    {
        //保存节点
        struct ListNode* next=cur->next;

        //头插
        cur->next=newnode;
        newnode=cur;
        cur=next;
    }
    return newnode;
}

五、合并两个有序链表

题目：

💡方法一：

我们创建一个带哨兵位的链表，这样在尾插时就不用判断是否是第一个节点，可以提高效率。要记住在最后要将哨兵位的空间释放。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1==NULL)
    {
        return list2;
    }


    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    //创建一个哨兵位
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next=list1;
            tail=tail->next;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=tail->next;
            list2=list2->next;
        }
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    struct ListNode* del=head;
    head=head->next;
    free(del);
    return head;
}