您的位置:首页 > 教程 > 开发工具 > sublime > C语言实题讲解快速掌握单链表上

C语言实题讲解快速掌握单链表上

2022-04-11 14:53:02 来源:易采站长站 作者:

C语言实题讲解快速掌握单链表上

目录
1、移除链表元素2、反转链表3、链表的中间节点4、链表中倒数第k个节点5、合并两个有序链表6、链表分割

1、移除链表元素

链接直达:

移除链表元素

题目:

思路:

此题要综合考虑多种情况,常规情况就如同示例1,有多个节点,并且val不连续,但是非常规呢?当val连续呢?当头部就是val呢?所以要分类讨论

常规情况:

需要定义两个指针prev和cur,cur指向第一个数据,prev指向cur的前一个。依次遍历cur指向的数据是否为val,若是,则把prev的下一个节点指向cur的下一个节点上,cur=cur->next,prev跟着cur一起走,直到cur走到NULL

连续val:

当我们仔细观察下,不难发现,在常规情况下是可以解决连续val的,但是头部val就不可了

头部val:

此时除了刚才定义的两个指针prev和cur外,还要有个head指向头部,当头部是val时,将cur指向下一个位置,head跟着一起动,直到cur指向的数据不为val时,将head赋给prev。此时剩余的就按常规处理即可。

代码如下:

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

2、反转链表

链接直达:

反转链表

题目:

思路:

法一:三指针翻转方向

定义三个指针n1,n2,n3分别用来指向NULL,第一个数据,第二个数据。让n2的next指向n1,把n2赋给n1,再把n3赋给n2,再执行n3=n3->next的操作,接下来重复上述操作,直到n2指向空即可。但是要注意,要先判断该链表是否为NULL,如果是,则返回NULL,此外,还要保证当n3为空时就不要动了,直接把n3赋给n2即可。

代码如下:

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*n1=NULL;
    struct ListNode*n2=head;
    struct ListNode*n3=n2->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        {
            n3=n3->next;
        }
    }
    return n1;
}

法二:头插

此法就需要再创建一个链表了,创建一个新的头部newhead指向NULL,再定义一个指针cur指向原链表第一个数据,注意还得定义一个指针next指向cur的下一个节点。遍历原链表,把节点取下来头插到newhead所在的链表。每次更新newhead赋给cur,如图所示:

 代码如下:

struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*cur=head;
    struct ListNode*next=cur->next;
    struct ListNode*newhead=NULL;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        {
            next=next->next;
        }
    }
    return newhead;
}

3、链表的中间节点

链接直达:

链表的中间节点

题目:

 思路:

快慢指针

这道题要注意奇偶数,如果为奇数,如示例1,那么中间节点值就是3,反之偶数如示例2,返回第二个中间节点。此题我们定义两个指针slow和fast都指向第一个数据的位置,区别在于让slow一次走1步,fast一次走2步。当fast走到尾指针时,slow就是中间节点

 代码如下:

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

4、链表中倒数第k个节点

链接直达:

链表中倒数第k个节点

题目:

 思路:

快慢指针

定义两个指针slow和fast,让fast先走k步,再让slow和fast同时走,当fast走到尾部时,slow就是倒数第k个,因为这样的话slow和fast的差距始终是k个,当fast走到空时结束。此题同样可以走k-1步,不过当fast走到尾部时结束,也就是fast的下一个节点指向空时结束,都一样。先拿走k步举例,如图所示:

 代码如下:

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    while(k--)
    {
        //if判断,防止k大于链表的长度
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

5、合并两个有序链表

链接直达:

合并两个有序链表

题目:

 思路:

法一:归并(取小的尾插)--- 带头节点

假设新链表的头叫head并指向NULL,还需要定义一个指针tail来方便后续的找尾,依次比较list1和list2节点的值,把小的放到新链表head上,并更新tail,再把list1或list2更新一下。当list1和list2两个链表中一个走到空时,直接把剩下的链表所有剩下的元素拷进去即可

 代码如下:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    //检查list1或list2一开始就为NULL的情况
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    struct ListNode*head=NULL;
    struct ListNode*tail=head;
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(tail==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=list1;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }
    }
    //当list1和list2其中一个走到空的情况
    if(list1==NULL)
    {
        tail->next=list2;
    }
    else
    {
        tail->next=list1;
    }
    return head;
}

法二:哨兵位的头节点

解释下带头节点:

比如说同样一个链表存1,2,3。不带头节点只有这三个节点,head指向1。而带头节点的同样存3个值,不过有4个节点,head指向头部这个节点,这个节点不存储有效数据

 带头结点有如下好处,不用判断head和tail是否为空了,也不用判断list1和list2是否为空了,会方便不少。和上述思路一样,取小的下来尾插,直接链接到tail后面即可。但是要注意返回的时候要返回head的next,因为题目给的链表是不带头的,而head本身指向的就是那个头,所以要返回下一个。

代码如下:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = NULL, * tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    while (list1 && list2)
    {
        if (list1->val < list2->val)
        {
            tail->next = list1;
            tail = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = list2;
            list2 = list2->next;
        }
    }
    //当list1和list2其中一个走到空的情况
    if (list1 == NULL)
    {
        tail->next = list2;
    }
    else
    {
        tail->next = list1;
    }
    struct ListNode* list = head->next;
    free(head);
    head = NULL
        return list;
}

6、链表分割

链接直达:

链表分割

题目:

 思路:

定义两个链表lesshead和greaterhead。遍历原链表,把 < x 的插入到链表1,把 > x 的插入到链表2,最后再把链表1和链表2链接起来。在定义两个尾指针以跟进链表1和2新增元素

 代码如下:

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greaterTail->next = NULL;
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        //合并
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greaterHead);
        return list;
    }
};

到此这篇关于C语言实题讲解快速掌握单链表上的文章就介绍到这了,更多相关C语言 单链表内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站!

如有侵权,请联系QQ:279390809 电话:15144810328

相关文章

  • sublime php语法错误提示怎么发现

    sublime php语法错误提示怎么发现

    sublime php语法错误提示的发现方法:首先打开sublime软件;然后在sublime中写入php代码;接着按下快捷键“ctrl+B”,即可在执行过程中显示错误提示。昨晚因为php的某个变量代码写错了,sublime又没有提示语法错误。弄了许久,一段段的调试,最后才知道是取到的变量是空的sublime可以提示php语法错误在sublime写完了php代码后,如果写错了不像eclipse即时
    2020-08-15
  • Sublime Text3简体中文汉化包怎么用

    Sublime Text3简体中文汉化包怎么用

    下面由sublime教程栏目给大家介绍Sublime Text3简体中文汉化包的使用方法,希望对需要的朋友有所帮助!汉化包下载地址:https://github.com/Trojain/sublime-package1、由上面的链接得到的 Default.sublime-package 文件。打开sublime text 3 编辑器,打开菜单 => preferences => Browse Pa
    2020-08-20
  • 关于 Sublime Text 中的 Git

    关于 Sublime Text 中的 Git

    下面由sublime教程栏目给大家介绍Sublime Text 中的 Git,希望对需要的朋友有所帮助!Sublime Text 中的 Git从 3.2 版本开始,Sublime Text 在编辑器内集成了 Git。功能如下:侧边栏将会使用图标来指明文件及文件夹的 Git 状态。被你的 .gitignore 文件所指定忽略的文件以及文件夹会在侧边栏褪色显示。在状态栏,你能够查看当前所在分支以及你做
    2020-08-21
  • Sublime Text3+Markdown配置步骤【图文详解】

    Sublime Text3+Markdown配置步骤【图文详解】

    下面由sublime教程栏目给大家介绍Sublime Text3+Markdown配置步骤【图文详解】,希望对需要的朋友有所帮助!Sublime是一款非常优秀的文本编辑器,可以安装大量的插件,使用Sublime + Markdown更是有一番别样体验,在此只写如何正确配置(以Sublime Text 3为例),使用技巧请参阅相关文章。1.安装Package:Markdown Preview和Ma
    2020-08-22
  • 三步搞定sublime text 3配置

    三步搞定sublime text 3配置

    下面由sublime教程栏目给大家介绍sublime text 3的下载和配置,希望对需要的朋友有所帮助!下载sublime text 3在百度中搜索sublime text 3,进入sublime text官网,官网链接是http://www.sublimetext.com/。下载界面如图所示:点击Download for Windows按钮,下载sublime text 3,需要注意的是这里下
    2020-08-24
  • 分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色)

    分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色)

    下面由sublime教程栏目给大家分享Sublime Text 3 、WebStorm配置护眼主题(浅绿色),希望对需要的朋友有所帮助!本文所用软件版本Sublime Text 3(Build 3143)、WebStorm 2017.2.4(Build #WS-172.4155.35),其他版本软件配置过程可能不一样,请知悉!1.Sublime Text 3护眼主题 (1)下载配置文件 链
    2020-08-26
  • Sublime Merge 是什么

    Sublime Merge 是什么

    下面由sublime教程栏目给大家介绍Sublime Merge,希望对需要的朋友有所帮助!Sublime Merge 是由知名文本编辑器 Sublime Text 开发商打造的 Git 客户端,仅适用于 64 位平台。按开发商的说法,Sublime Merge 融合了 Sublime Text 的 UI 引擎和从零开始的 Git* 实现。所以这一工具继承了 Sublime Text 优雅美观的
    2020-08-27
  • Sublime Text 快捷键列表分享

    Sublime Text 快捷键列表分享

    下面由sublime教程栏目给大家介绍Sublime Text 快捷键,希望对需要的朋友有所帮助!Sublime Text 快捷键列表 快捷键按类型分列如下:1、通用 ↑↓← → 上下左右移动光标 Alt 调出菜单 Ctrl + Shift + P 调出命令板(Command Palette) Ctrl + ` 调出控制台2
    2020-08-29