反转链表__牛客网

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： $0\leq n\leq1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

数据结构和算法

发表于 2020-12-21 17:00:46

精华题解 1，使用栈解决链表的反转是老生常谈的一个问题了，同时也是面试中常考的一道题。最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下 import java.util.Stack; publ 展开全文

Gemini48

发表于 2021-07-15 15:53:13

精华题解解法一：迭代在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。图解： Java参考代码： /* public class ListNode { int v 展开全文

大菠萝侦探

发表于 2021-06-26 11:31:23

精华题解描述输入一个链表，反转链表后，输出新链表的表头。方法一因为链表结尾是 null，所以让 pre 的值是 null, p 就表示我们的头部因为 p 的 next 成员马上就要指向 pre, 如果不保存 p 的下一个节点就会使其丢失，所以通过临时变量 t 保存它让 P 的 next 成员展开全文

Maokt

发表于 2021-06-23 17:32:16

精华题解算法思想一：双指针迭代解题思路：（1）定义两个指针： pre 和 cur ；pre 在前 cur 在后。（2）每次让 pre 的 next 指向 cur ，实现一次局部反转（3）局部反转完成之后， pre 和 cur 同时往前移动一个位置（4）循环上述过程，直至 pre 到达链展开全文

开车的阿Q

发表于 2021-06-21 23:07:12

精华题解描述这是一篇面对初级coder的题解。知识点：链表栈难度：一星题解题目：输入一个链表，反转链表后，输出新链表的表头。考察链表的基础知识方法一：栈利用栈后进先出的特性，可以实现链表翻转 #includeclass Solution { 展开全文

2019113916

发表于 2021-07-18 17:41:09

精华题解方法一：新建链表 1.结题思路看到这道题，最容易想到的应该就是保存链表指针或者权值，构造新的链表，题目是简单题，很容易AC。 2.解法 vector容器保存节点指针。然后先令头指针指向最后一个结点，从倒数第二个元素开始反向遍历vector，后插法建立新的链表。 3.图解 4.具体代码 List 展开全文

大菠萝侦探

发表于 2021-06-23 16:40:01

精华题解描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。算法比较方便的做法是设置一个虚拟节点 fake，而它的 next 指向的地址才是真正的表头，然后开始的时候将它作为 pre 指针。在循环中，每次都将要接入的新节点接到 pre 后面，然后更新 pre 展开全文

未来0116

发表于 2021-07-18 19:01:15

精华题解一.题目描述NC78反转链表题目链接:https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=188&&tqId=38547&rp=1&ru=/activity/oj&qr 展开全文

2019113913

发表于 2021-07-18 19:16:56

精华题解题意思路：输入一个链表，反转链表后，输出新链表的表头。方法一：调整链表指针，反转链表 pre指针指向已经反转好的链表的最后一个节点，初始化为null； cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向头指针； next指针指向待反转链表的第二个节点，目的是保存链表，因为cu 展开全文

牛客500979850号

发表于 2021-07-15 22:01:07

精华题解方法一：将链表中的值提取出来，然后分配新的链表节点组成新链表。代码如下： class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode *p,*t; int q; // 展开全文

牛客题解官

发表于 2020-05-29 15:13:44

描述这是一篇针对初学者的题解，共用2种方法解决。知识点：单链表难度：一星题解方法一：构造链表如果此类型的题出现在笔试中，如果内存要求不高，可以采用如下方法：可以先用一个vector将单链表的指针都存起来，然后再构造链表。此方法简单易懂，代码好些。###代码： class Solution 展开全文

伊万夫斯基

发表于 2019-08-24 18:22:21

以3个节点为例：用pre记录当前节点的前一个节点用next记录当前节点的后一个节点当前节点a不为空，进入循环，先记录a的下一个节点位置next = b;再让a的指针指向pre 移动pre和head的位置，正因为刚才记录了下一个节点的位置，所以该链表没有断，我们让head走向b的位置。当展开全文

道阻且长z

发表于 2019-09-26 00:33:52

思路：题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null; 知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。这就需要把结点挨个从链表上摘下来，做调整；这个调整过程需要两个指针展开全文

ccจุ๊บ

发表于 2020-02-25 18:03:46

时间复杂度O(n) class Solution: # 返回ListNode def ReverseList(self, pHead): # write code here if not pHead: return None 展开全文

Khan201803011945114

发表于 2021-09-26 16:29:29

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回ListNo 展开全文

牛客681393164号

发表于 2021-11-08 00:10:15

python语法糖，不用白不用 def ReverseList(self , head: ListNode) -> ListNode: if not head: # 如果非空 return head a, a.next, b =h 展开全文

爱敲代码的小黄

发表于 2020-04-02 15:27:01

欢迎访问我的个人博客：苦酒 1. 题目描述输入一个链表，反转链表后，输出新链表的表头。 2. 题目分析链表如下所示：. 首先，定义三个结点，分别指向如下： p1 = null;p2 = head;p3 = head.next;3. 将p2.next(此刻连接1-2的剪头)指向p1，如下所示展开全文

牛客题解官

发表于 2022-04-22 10:58:10

题目的主要信息：给定一个长度为nnn的链表，反转该链表，输出表头举一反三：学习完本题的思路你可以解决如下题目： JZ6. 从尾到头打印链表方法一：迭代（推荐使用）思路：将链表反转，就是将每个表元的指针从向后变成向前，那我们可以遍历原始链表，将遇到的节点一一指针逆向即可。指针怎么逆向？展开全文

没有实习的鱼

发表于 2022-04-18 17:58:23

/*function ListNode(x){ this.val = x; this.next = null; }*/ function ReverseList(pHead) { // write code here let prev=null let cur 展开全文

美丽东

发表于 2019-08-21 10:47:26

链表反转，我首先想到的就是头插法。在这里提供两种头插法思路。一种是操作指针，一种是操作数值。指针操作 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val( 展开全文

反转链表

输入

输出

输入

输出

说明

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题