反转链表的四种方法(C语言)

这篇具有很好参考价值的文章主要介绍了反转链表的四种方法(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

反转链表c语言,链表,c语言,数据结构,算法

输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]

示例 2:

反转链表c语言,链表,c语言,数据结构,算法

输入:head = [1,2] 输出:[2,1]

示例 3:

输入:head = [] 输出:[]

提示:

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

方法一 原地反转

本题链表不带头结点
原地反转需要两个指针,以防pre指针操作后指向上一节点而丢失指向下一节点的指针
反转链表c语言,链表,c语言,数据结构,算法

pre->next = cur->next:1.连:第一步先将pre所在节点和cur->next所在节点连接起来,将当前节点 cur 从链表中移除,并把链表连接起来。
反转链表c语言,链表,c语言,数据结构,算法
cur->next = head;2.掉:将cur的next指向head,将cur插入到head的前面,以便将其放置到链表的前面,成为新的头节点。 反转链表c语言,链表,c语言,数据结构,算法

head = cur;3.接:更新head,使其指向当前的cur
反转链表c语言,链表,c语言,数据结构,算法

cur = pre->next;4.移:更新cur,移动到下一个待反转的节点
反转链表c语言,链表,c语言,数据结构,算法

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

方法二 迭代

temp保存cur的下一个节点,以防止反转时丢失链表信息。
反转链表c语言,链表,c语言,数据结构,算法

cur->next = pre;cur的下一个指针指向pre,实现反转。
反转链表c语言,链表,c语言,数据结构,算法

更新pre为当前的cur,为下一次迭代做准备。
更新cur为保存的下一个节点temp,继续迭代。
反转链表c语言,链表,c语言,数据结构,算法
通过不断改变指针的指向将链表进行反转。pre充当新链表的头节点,当curNULL循环停止,返回pre

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) {
        struct ListNode* temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

方法三 递归

我们可以通过迭代的方法来得到递归方法
观察reverse函数,
函数声明中pre指针指向的为NULL,cur指针指向的为head,正如递归中声明并初始化的precur指针
递归结束条件为curNULL,返回pre
同样temp保存cur的下一个节点,以防止反转时丢失链表信息。
然后进行反转cur->next = pre;
pre 为当前已反转部分的头节点,cur为当前待反转的节点。
然后调用递归,将cur作为新的pre传入下一层,将temp作为新的cur传入下一层。
实现了链表的递归反转

struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) {
    if (!cur){
        return pre;
    }
    struct ListNode* temp = cur->next;
    cur->next = pre;
    //将cur作为pre传入下一层
    //将temp作为cur传入下一层,改变其指针指向当前cur
    return reverse(cur, temp);
}

struct ListNode* reverseList(struct ListNode* head) {
    return reverse(NULL, head);
}

方法四 新建链表法

struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = head->val;
新建一个链表,并初始化
newNode->next = newHead;将新节点插入到新链表的头部

反转链表c语言,链表,c语言,数据结构,算法
newHead = newNode;
反转链表c语言,链表,c语言,数据结构,算法
head = head->next;
反转链表c语言,链表,c语言,数据结构,算法
遍历原链表,使用头插法新建链表,并不断移动newHead指针,当原链表头指针指向NULL最终返回newHead


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = NULL;
    while (head) {
        // 创建一个新节点
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = head->val;        
        // 将新节点插入到新链表的头部
        newNode->next = newHead;
        newHead = newNode;
        // 移动到原链表的下一个节点
        head = head->next;
    }
    return newHead;
}


感谢您的阅读文章来源地址https://www.toymoban.com/news/detail-841704.html

到了这里,关于反转链表的四种方法(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 对比编程语言的四种错误处理方法,哪种才是最优方案?

    作者:Andrea Bergia 译者:豌豆花下猫@Python猫 英文:Error handling patterns 转载请保留作者及译者信息! 错误处理是编程的一个基本要素。除非你写的是“hello world”,否则就必须处理代码中的错误。在本文中,我将讨论各种编程语言在处理错误时使用的最常见的四种方法,并分析

    2024年02月03日
    浏览(76)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(202)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(72)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(82)
  • 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

    /**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* reverseList(ListNode* head) {              } };

    2024年02月22日
    浏览(49)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(65)
  • 详解链表oJ<反转链表,链表的中间节点及链表的回文>

    hello,大家好,这里是Dark FlameMaster,今天和大家分享的是有关数据结构链表的几道题目,链表的中间节点,反转链表及判断链表是否为回文结构,放在一起讲解会印象更加深刻。 链接:链表的中间节点 分析:  如果想要得到链表的中间节点,最简单的思路就是从头结点遍历整

    2024年02月08日
    浏览(65)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(83)
  • 【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

      目录 一.【Leetcode206】反转链表 1.链接 2.题目再现  3.解法A:三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现  3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现  3.解法 1.链接 反转链表 2.题目再现  3.解法

    2024年02月02日
    浏览(48)
  • 【算法入门&链表】【模板】链表|反转链表|合并排序链表|删除链表的节点

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月17日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包