【数据结构】单链表OJ题(一)

在这里插入图片描述
🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

在这里插入图片描述

文章目录

前言
一、移除链表元素
二、寻找链表中间结点
三、输出链表倒数第k个结点
四、反转单链表
五、合并两个有序链表

前言

在上一期中我们介绍了单链表，也对单链表的实现进行具体的了解，接下来我们开始单链表的练习，对单链表更深层的理解，让小伙伴们灵活的使用单链表，话不多说，开造~

一、移除链表元素

在这里插入图片描述

💭方法一：

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

常规删除：

在这里插入图片描述

头节点删除：

在这里插入图片描述

思路：(1)首先给出判断cur是否是空的，不是空的之后，判断是否有val，有的话就判断是否在头部，是的话一种情况，不是的话，又是一种情况。（2）第一种情况，题意所给出的情况；第二种情况，中间连续个value（前两种可以合并）；第三种情况，一开始就出现6或者连续个6；第四种情况：空的

struct ListNode* removeElements(struct ListNode* head, int val)
{
    if (head == NULL)
        return head;
    struct ListNode* prev = NULL, * cur = head;
    while (cur)
    {
        struct ListNode* Next = cur->next;
        if (cur->val == val)
        {
            if (prev == NULL)
            {
                head = Next;
                cur = Next;
            }
            else
            {
                prev->next = Next;
                free(cur);
                cur = Next;
            }
        }
        else
        {
            prev = cur;
            cur = Next;
        }
    }
    return head;
}

💭方法二：

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

truct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* newnode=NULL;
    struct ListNode* cur=head,*tail=newnode;
    while(cur)
    {
        if(cur->val!=val)
        {
            if(tail==NULL)
            {
                newnode=cur;
                tail=newnode;
            }
            else
            {
                tail->next=cur;
                tail=tail->next;
            }
            cur=cur->next;
        }
        else
        {
            struct ListNode* del=cur;
            cur=cur->next;
            free(del);
        }
    }
    if(tail)
    {
        tail->next=NULL;
    }
    return newnode;
}

二、寻找链表中间结点

在这里插入图片描述

我们可以定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到结尾时，慢指针正好走了一半，这样我们就可以找到中间节点。

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

三、输出链表倒数第k个结点

在这里插入图片描述

我们可以参考上一题的方法，同样定义快慢指针，先让快指针走k步，然后再同时走，走到fast为空指针就找了倒数第k个节点。有可能链表没有k个节点，所以我们要加入判断。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow=pListHead,*fast=pListHead;
    while(k--)
    {
        if(fast==NULL)
        {
            return NULL;
        }
        fast=fast->next;
    }
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

四、反转单链表

在这里插入图片描述

💭方法一：

我们定义三个指针n1,n2,n3，来改变节点链接的顺序。将头节点变为尾节点，当n2为空指针时，n1就为链表的头节点，只需返回n1就可以。两个指针倒方向，一个指针保持下一个。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1=NULL,*n2=head,*n3=NULL;
    if(head==NULL)
        return head;
    while(n2)
    {
        n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    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;
    while(list1&&list2)
    {
        if((list1->val) < (list2->val))
        {
            if(tail==NULL)
            {
                head=list1;
                tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=list1;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=list2;
                tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }
    }
    if(list1)
        tail->next=list1;
    if(list2)
        tail->next=list2;
    return head;
}

有头单链表：head->next指的是第一个节点的地址（带头，相当于开头多了一个节点，但是节点里面的val不确定，next指向下一个节点）；无头单链表：head指的是第一个节点的地址； OJ题默认不带头

💭代码二：（带头）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头
    struct ListNode* tail = head;
    head->next = NULL;//就是含有值的节点的第一个
    while (list1 && list2)
    {
        struct ListNode* next1 = list1->next;
        struct ListNode* next2 = list2->next;
        if ((list1->val) < (list2->val))
        {
            tail->next = list1;
            tail = list1;
            list1 = next1;
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = next2;
        }
    }

    if (list1 != NULL)
    {
        tail->next = list1;

    }
    if (list2 != NULL)
    {
        tail->next = list2;
    }
    struct ListNode* list = head->next;
    free(head);
    return list;
}