力扣206. 反转链表

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

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

示例 1:

力扣206. 反转链表,面试题,面试,算法,leetcode,链表,算法

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

示例 2:

力扣206. 反转链表,面试题,面试,算法,leetcode,链表,算法

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

示例 3:

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

提示:

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

进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

思路

如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

力扣206. 反转链表,面试题,面试,算法,leetcode,链表,算法

之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向。

那么接下来看一看是如何反转的呢?

我们拿有示例中的链表来举例

首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。

然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。

为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。

接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。

最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。

 Java:

// 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}
// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}
// 从后向前递归
class Solution {
    ListNode reverseList(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;
        
        // 递归调用,翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点,next 需要指向 NULL
        head.next = null;
        return last;
    } 
}

使用虚拟头结点解决链表翻转

使用虚拟头结点,通过头插法实现链表的翻转(不需要栈)

// 迭代方法:增加虚头结点,使用头插法实现链表翻转
public static ListNode reverseList1(ListNode head) {
    // 创建虚头结点
    ListNode dumpyHead = new ListNode(-1);
    dumpyHead.next = null;
    // 遍历所有节点
    ListNode cur = head;
    while(cur != null){
        ListNode temp = cur.next;
        // 头插法
        cur.next = dumpyHead.next;
        dumpyHead.next = cur;
        cur = temp;
    }
    return dumpyHead.next;
}

使用栈解决反转链表的问题

  • 首先将所有的结点入栈
  • 然后创建一个虚拟虚拟头结点,让cur指向虚拟头结点。然后开始循环出栈,每出来一个元素,就把它加入到以虚拟头结点为头结点的链表当中,最后返回即可。
public ListNode reverseList(ListNode head) {
    // 如果链表为空,则返回空
    if (head == null) return null;
    // 如果链表中只有只有一个元素,则直接返回
    if (head.next == null) return head;
    // 创建栈 每一个结点都入栈
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = head;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    // 创建一个虚拟头结点
    ListNode pHead = new ListNode(0);
    cur = pHead;
    while (!stack.isEmpty()) {
        ListNode node = stack.pop();
        cur.next = node;
        cur = cur.next;
    }
    // 最后一个元素的next要赋值为空
    cur.next = null;
    return pHead.next;
}

采用这种方法需要注意一点。就是当整个出栈循环结束以后,cur正好指向原来链表的第一个结点,而此时结点1中的next指向的是结点2,因此最后还需要cur.next = null文章来源地址https://www.toymoban.com/news/detail-593715.html

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

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

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

相关文章

  • leetcode 206.反转链表

    ✨链接:数据结构-手撕单链表+代码详解。 🌟 leetcode链接:反转链表 1️⃣ 代码: 2️⃣ 代码:

    2024年02月12日
    浏览(38)
  • LeetCode:206. 反转链表

    力扣链接

    2024年01月15日
    浏览(44)
  • 链表反转-LeetCode206

    题目: 给你单链表的头结点head,请反转链表,并返回反转后的链表。 示例: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 1、建立虚拟头结点辅助反转 分析链表插入元素的时候,会发现如何处理头结点是个比较麻烦的问题,为此可以先建立一个虚拟的结点ans,并且令a

    2024年02月07日
    浏览(43)
  • Leetcode-每日一题【206.反转链表】

    给你单链表的头节点  head  ,请你反转链表,并返回反转后的链表。 示例 1: 输入: head = [1,2,3,4,5] 输出: [5,4,3,2,1] 示例 2: 输入:head = [1,2] 输出:[2,1] 示例 3: 输入:head = [] 输出:[] 提示: 链表中节点的数目范围是 [0, 5000] -5000 = Node.val = 5000   1.我们遍历链表,首先设置

    2024年02月12日
    浏览(37)
  • 206. 反转链表、Leetcode的Python实现

    博客主页:🏆 看看是李XX还是李歘歘  🏆 🌺每天分享一些包括但不限于计算机基础、算法等相关的知识点🌺 💗 点关注不迷路,总有一些📖知识点📖是你想要的 💗 ⛽️今天的内容是      Leetcode    206. 反转链表     ⛽️💻💻💻 206. 反转链表 给你单链表的头节点 

    2024年02月06日
    浏览(36)
  • 反转链表 Java版 图文并茂思路分析带答案(力扣第206题)

    力扣第206题 我们不只是简单的学习(背诵)一个数据结构,而是要分析他的思路,以及为什么要有不同的指针等等 思路分析:首先要链表有个头指针没有任何问题 然后,我们要将1的下一个节点指向空,这样才能将其反转过来,但是这个时候我们发现和下一个节点2失去了联

    2024年02月05日
    浏览(42)
  • 刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解 参与链接在此 : https://programmercarl.com/other/xunlianying.html 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个

    2023年04月09日
    浏览(51)
  • 【Leetcode60天带刷】day03链表——203. 移除链表元素,707.设计链表,206. 反转链表

    链表就像一串小火车,有一节一节的车厢,每个车厢都叫做一个节点。  单链表:每个链表车厢里有两个内容,一个放的是真正的数据,另一个放的是下一节车厢的编号。 双链表:每个链表车厢里有三个内容,一个真正数据,一个下一个车厢的编号,还有一个上一节车厢的编

    2024年02月06日
    浏览(49)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(53)
  • 【LeetCode题目详解】 203. 移除链表元素707. 设计链表206. 反转链表 day3(补)

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 看到这道题就想到了链表 这道题有两种写法,涉及如下链表操作的两种方式: 直接使用

    2024年02月16日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包