【LeetCode】反转链表（206. 题）| 图解算法，动图演示，超详细哦~

glumes 发布于2021-09-03 10:29 / 1433人阅读

摘要：文章目录题目描述解题思路解法调整节点指针的方向解法头插法题目难度简单题目描述给你单链表的头节点，请你反转链表，并返回反转后的链表。

文章目录

题目难度：《简单》

（1）题目描述

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

示例1：

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

输出：[5,4,3,2,1]

示例2：

输入：head = [1,2]

输出：[2,1]

示例3：

输入：head = [ ]

输出：[ ]

LeetCode链接：206. 反转链表

（2）解题思路

1）解法1：调整节点指针的方向

步骤

定义一个指针 cur，用来遍历链表
定义一个指针 prev，保存 cur 的上一个节点的位置，初始指向 NULL
定义一个指针 next，保存 cur 的下一个节点的位置，用来迭代

通过 prev 和 cur 来调整每个节点指针的方向，next 进行迭代

最后返回头节点指针 head 即可

代码如下

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head){    //解题思路：把链表中所有节点的next指针指向反转    struct ListNode* prev = NULL;  //保存cur的上一个节点的位置    struct ListNode* cur = head;   //遍历链表    while(cur != NULL)    {        struct ListNode* next = cur->next;  //保存cur的下一个节点位置        cur->next = prev;  //调整当前节点next指针的方向        prev = cur;        cur = next;    }    head = prev;  //更新头节点    return head;}

2）解法2：头插法

然后把链表中的所有节点依次头插到一个新链表中，相当于反转了原链表

定义一个指针 cur，用来遍历原链表
定义一个指针 next，保存 cur 的下一个节点的位置
定义一个指针 newhead，指向新链表的头节点

动图演示

代码如下

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* reverseList(struct ListNode* head){    //解题思路：把链表中的所有节点依次头插到一个新链表中，相当于反转了原链表    //当链表为空或链表只有一个节点时    if(head == NULL || head->next == NULL)    {        return head;    }    struct ListNode* newhead = NULL;    struct ListNode* cur = head;    while(cur)    {        //保存cur当前所在节点的下一个节点的位置        struct ListNode* next = cur->next;        cur->next = newhead;  //开始头插        newhead = cur;  //更新头节点        cur = next;  //cur指向下一个待插入的节点    }    return newhead;}

大家快去动手练习一下吧！

专线服务私有云 python反转链表 centos7安装详细图解排序算法图解链表算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/118983.html

Chain Surfase Test - java 链表经典 OJ 面试题 - 巨细

摘要：新链表是通过拼接给定的两个链表的所有节点组成的。保证链表长度小于等于。注意，函数返回结果后，链表必须保持其原始结构。注意不作为参数进行传递，仅仅是为了标识链表的实际情况。如果是，则在该链表中没有环。说明不允许修改给定的链表。 ...

aristark 2021-11-11 16:54 评论0 收藏0
LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

摘要：算法思路两种方法一般反转递归法一般解决定义三个指针，分别为，存储当前结点，指向反转好的结点的头结点，存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时，返回当前节点判断当前的链表是否为递归找到尾结点，将其存储为头结点。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿题目：Reverse...

zhangfaliang 2019-08-23 17:12 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 61：旋转链表 Rotate List

摘要：给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。只需在第个节点之后切断，首尾连接即可。另外可能大于链表长度，应当做求余运算。给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 Given a linked list, rotate the list to the ...

Hwg 2019-07-31 11:30 评论0 收藏0