首页 > 其他分享 >206. 反转链表

206. 反转链表

时间:2023-12-15 18:00:12浏览次数:30  
标签:head ListNode temp 206 反转 next 链表 null 节点

题目

206. 反转链表

要求

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

答案

这道题目也是使用虚拟节点,我先使用虚拟节点做了一遍,结果如下,就是想清楚在循环的时候保留当前节点就可以:

public static ListNode reverseList(ListNode head) {
    ListNode virtual = new ListNode(0);
    while (head != null) {
        // 先保留当前节点
        ListNode virtualNode = head;
        // 更换头指针
        head = head.next;
        // 更换虚拟节点的下个节点
        virtualNode.next = virtual.next;
        // 维护外围虚拟节点
        virtual.next = virtualNode;
    }
    return virtual.next;
}

官方题解的递归思路有点烧脑,我看了半天没看懂,然后 debug 看了一下才明白:

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode temp = reverseList2(head.next);
    head.next.next = head;
    head.next = null;
    return temp;
}

递归思路我能看懂 ListNode temp = reverseList2(head.next);,看不懂的是head.next.next = head;head.next = null;,下面举例说明:原始的链表是 1→2→3→4→5→null.现在递归,到最后一个节点返回,这个时候 temp 是 5,head 是 4,在执行完 head.next.next = head;之后,其实修改的是 5 节点,也就是修改完之后,temp 的内容为 5→4→5→4····,执行完 head.next = null 之后,temp 的结果为 5→4→nul

现在看看继续倒数第二轮,这个时候 temp 为 5→4→null,head 为 3→4→null,执行完 head.next.next = head; 其实就是修改了 4 节点,把 4 的 next 修改为 3,结果为 3→4→3→4→3······,注意,这个时候 temp 为 5→4→3→4→3→······,执行完 head.next = null;之后,temp 的结果为 5→4→3→null,由此可以看出规律来。

其实在每一次执行完 head.next.next = head; 之后都会形成一个环,下一个head.next = null; 就是为了破除环,其实这块有一个对象引用的问题需要熟悉了解,head.next.next 其实修改的是 temp 的尾节点,head.next 是在前一个基础上修改 temp 的尾节点的 next 为 null,避免出现了环。这个确实不太好理解,debug 看更清楚一点。

标签:head,ListNode,temp,206,反转,next,链表,null,节点
From: https://www.cnblogs.com/wadmwz/p/17903918.html

相关文章

  • 707. 设计链表
    题目:707.设计链表要求:你可以选择使用单链表或者双链表,设计并实现自己的链表。单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果是双向链表,则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点......
  • Nestjs 依赖注入和控制反转
    前言Nest.js是一个使用TypeScript实现的在Node.js环境中运行的Web服务开发框架。它借鉴了很多优秀的设计思想,本文来说一说Nest中的依赖注入和控制反转。依赖注入依赖注入,英文名是DependencyInjection,简称DI。什么是依赖注入?可以分开来看,就是“依赖”和“注入”。您可能......
  • 203. 移除链表元素
    题目:203.移除链表元素要求:给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。解答:独自写出来了,但是代码=写的不好,我的思路是分两步,第一步先把头节点等于目标值的节点全部删除,第二步在遍历后续节点,删除等于目标值......
  • 【删除排序链表中的重复元素】模拟
    leetcode82.删除排序链表中的重复元素II题意:只要链表中元素x重复出现了,删除所有元素x(刚开始还读错题了……)题解:在表头前添加链表的虚拟节点dummy遍历链表(1)如果当前节点cur的下一个节点cur.next和cur.next.next相等,则意味着出现了重复元素,记录元素值,从cur.next开始挨个删......
  • 【合并排序链表】分治/优先队列
    合并两个排序链表模拟维护一个合并链表,每次添加两个排序链表中较小val的节点即可模拟代码publicListNodemergeTwo(ListNodea,ListNodeb){if(a==null)returnb;if(b==null)returna;ListNodeans=newListNode(0);Lis......
  • 【删除链表的倒数第N个节点】双指针
    leetcode19.删除链表的倒数第N个结点题解1:通过链表长度获取[倒数第n个节点]位置计算链表长度找到[倒数第N个节点]的前一个节点删除[倒数第N个节点]注意特殊情况:删除的是第一个节点时,直接返回第二个节点即可点击查看代码/***Definitionforsingly-linkedlist.......
  • 【大数相加链表模拟】
    leetcode2.两数相加题意:两个长度为[1,100]的大数,分别倒序存储(个位在链表头)在两个链表中,计算两个数的和,并倒序存储在一个新链表,返回链表表头。数据中不存在前导零。题解:模拟大数相加,注意维护进位carry即可代码/***Definitionforsingly-linkedlist.*publicclassL......
  • 【回文链表】快慢指针+反转链表
    leetcode234.回文链表题意:判断一个链表是不是回文(中心对称)的【反转链表】题解1:得到原链表的反转链表,然后对比原链表与反转链表的内容是否一致即可。反转链表版本代码/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNo......
  • 【反转链表】while循环/递归
    leetcode206.反转链表题意:给定链表表头,反转链表,返回反转链表的表头【循环】题解:head维护原链表当前节点,nHead维护反转链表的头节点,nHead置于head前一位,依次后移,直至head到链表尾结束。双指针循环版本/***Definitionforsingly-linkedlist.*publicclassListNode......
  • 数据结构:双链表
    由于双链表中大部分操作其实和单链表操作类似,所以这里只挑关键的一些函数1、定义与初始化typedefstructDNode{ElementTypedata;structDNode*prior,*next;}DNode,*DLinkList;boolInitialDLinkList(DLinkList&L){L=(DNode*)malloc(sizeof(DNode));......