首页 > 试题广场 >

反转链表

[编程题]反转链表

热度指数：1761422 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

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

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

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

示例1

输入

{1,2,3}

输出

{3,2,1}

示例2

输入

{}

输出

{}

说明

空链表则输出空

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

算法知识视频讲解

查看答案及解析

迭代版本（python3)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        next = None
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

递归版本（python3)：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        if not head &nbs***bsp;not head.next: return head
        h = self.ReverseList(head.next)
        head.next.next = head
        head.next = None
        return h

但是递归版本由于用例太长　栈溢出了

编辑于 2022-04-13 11:02:58 回复(0)

Python

sancery

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        p,c,n = None,pHead,None
        while c:
            n = c.next
            c.next = p
            p = c
            c = n
        return p

编辑于 2021-06-19 09:49:00 回复(0)

Python

GeorgeGate

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        curr = pHead
        prv = None
        while curr is not None:
            tmp = curr.next
            # 反转
            curr.next = prv
            # 更新 curr, prv
            prv = curr
            curr = tmp
        return prv

编辑于 2021-04-28 22:13:07 回复(0)

Python

牛客174791743号

代码

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead is None:
            return pHead
        p1 = pHead
        p2 = p1.next
        pHead.next = None
        while p2 is not None:
            p3 = p2.next
            p2.next = p1
            p1 = p2
            p2 = p3
        return p1

思路

初始状态

$\mathtt{(NULL)}\phantom{\rightarrow}\underset{\mathtt{pHead}}{\fbox{1}}\rightarrow\fbox{2}\rightarrow\fbox{3}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

开始循环前

`p1 = pHead`; `p2 = p1.next`

$\mathtt{(NULL)}\phantom{\rightarrow}\underset{\begin{array}{c}\mathtt{pHead}\\\color{red}{\mathtt{p1}}\end{array}}{\fbox{1}}\rightarrow\underset{\color{red}{\mathtt{p2}}}{\fbox{2}}\rightarrow\fbox{3}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`pHead.next = None`

$\mathtt{(NULL)}\color{red}{\leftarrow}\underset{\begin{array}{c}\mathtt{pHead}\\\mathtt{p1}\end{array}}{\fbox{1}}\phantom{\rightarrow}\underset{\mathtt{p2}}{\fbox{2}}\rightarrow\fbox{3}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

第一次循环

`p3 = p2.next`

$\mathtt{(NULL)}\leftarrow\underset{\mathtt{p1}}{\fbox{1}}\phantom{\rightarrow}\underset{\mathtt{p2}}{\fbox{2}}\rightarrow\underset{\color{red}{\mathtt{p3}}}{\fbox{3}}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p2.next = p1`

$\mathtt{(NULL)}\leftarrow\underset{\mathtt{p1}}{\fbox{1}}\color{red}{\leftarrow}\underset{\mathtt{p2}}{\fbox{2}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\fbox{3}}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p1 = p2`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\underset{\mathtt{p2}\\\color{red}{\mathtt{p1}}}{\fbox{2}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\fbox{3}}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p2 = p3`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\underset{\mathtt{p1}}{\fbox{2}}\phantom{\rightarrow}\underset{\mathtt{p3}\\\color{red}{\mathtt{p2}}}{\fbox{3}}\rightarrow\fbox{4}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

第二次循环

`p3 = p2.next`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\underset{\mathtt{p1}}{\fbox{2}}\phantom{\rightarrow}\underset{\mathtt{p2}}{\fbox{3}}\rightarrow\underset{\color{red}{\mathtt{p3}}}{\fbox{4}}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p2.next = p1`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\underset{\mathtt{p1}}{\fbox{2}}\color{red}{\leftarrow}\underset{\mathtt{p2}}{\fbox{3}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\fbox{4}}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p1 = p2`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\underset{\mathtt{p2}\\\color{red}{\mathtt{p1}}}{\fbox{3}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\fbox{4}}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

`p2 = p3`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\underset{\mathtt{p1}}{\fbox{3}}\phantom{\rightarrow}\underset{\mathtt{p3}\\\color{red}{\mathtt{p2}}}{\fbox{4}}\rightarrow\fbox{5}\rightarrow\mathtt{(NULL)}$

第三次循环

同第一次、第二次循环，过程省略

第四次循环

`p3 = p2.next`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\fbox{3}\leftarrow\underset{\mathtt{p1}}{\fbox{4}}\phantom{\rightarrow}\underset{\mathtt{p2}}{\fbox{5}}\rightarrow\underset{\color{red}{\mathtt{p3}}}{\mathtt{(NULL)}}$

`p2.next = p1`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\fbox{3}\leftarrow\underset{\mathtt{p1}}{\fbox{4}}\color{red}{\leftarrow}\underset{\mathtt{p2}}{\fbox{5}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\mathtt{(NULL)}}$

`p1 = p2`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\fbox{3}\leftarrow\fbox{4}\leftarrow\underset{\mathtt{p2}\\\color{red}{\mathtt{p1}}}{\fbox{5}}\phantom{\rightarrow}\underset{\mathtt{p3}}{\mathtt{(NULL)}}$

`p2 = p3`

$\mathtt{(NULL)}\leftarrow\fbox{1}\leftarrow\fbox{2}\leftarrow\fbox{3}\leftarrow\fbox{4}\leftarrow\underset{\mathtt{p1}}{\fbox{5}}\phantom{\rightarrow}\underset{\mathtt{p3}\\\color{red}{\mathtt{p2}}}{\mathtt{(NULL)}}$

此时，由于 p2 为空，因此退出循环。

函数返回 p1，即为反转后的链表的头。

补充：特殊情况

如果链表为空，则根据程序开头的判断，直接返回 pHead。

$\underset{\mathtt{pHead}}{\mathtt{(NULL)}}$

如果链表只有一个结点，则在进入循环之前，p2 已经为空，不会开始循环。因此，无需单独判断 pHead.next 是否为空。

$\underset{\mathtt{p2}}{\mathtt{(NULL)}}\leftarrow\underset{\begin{array}{c}\mathtt{pHead}\\\mathtt{p1}\end{array}}{\fbox{1}}$

编辑于 2021-04-22 16:48:08 回复(0)

Python

wengJJ

Python

递: 1->2->3 因为3.next=None 到达终止条件

归:

3 and 2->3->2 then 2->None so 3->2

2 and 1->2->1 then 1->None so 3->2->1

2020/6/12更新

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
#         2021/6/12 递归方法内存爆了已扑街
#         if not pHead&nbs***bsp;not pHead.next:
#             return pHead
#         pre = self.ReverseList(pHead.next)
#         pHead.next.next=pHead
#         pHead.next=None
#         return pre
#         迭代法
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        cur = pHead
        pre = None 
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

编辑于 2021-06-12 23:15:52 回复(0)

Python

Quinn_5400

增加一个链表,副本链表进行拷贝和指针指向调整即可

class Solution:

# 返回ListNode
def ReverseList(self, pHead):
# write code here
if not pHead:
return None
_p = pHead
_r = ListNode(_p.val)
_r.next = None
while _p:
# var
_p_t1 = _p.next
# ptr
if _p_t1:
_r_t1 = ListNode(_p_t1.val)
_r_t1.next = _r
_r = _r_t1
# next
_p = _p.next
return _r

发表于 2021-04-19 22:19:51 回复(0)

Python

牛客541273514号

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        p1=None
        pEnd=None
        while pHead:
            p1=pHead.next
            pHead.next=pEnd
            pEnd=pHead
            pHead=p1
        return pEnd

发表于 2021-04-16 17:40:25 回复(0)

Python

牛客973516059号

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        left=None
        right=pHead
        while right:
            right.next,right,left=left,right.next,right
        return left

发表于 2021-04-06 05:48:52 回复(0)

Python

HsiuQin

以空间换时间，用一个列表保存链表的值，然后逆序建立链表

发表于 2021-03-26 08:14:47 回复(0)

Python

熊sir

对链表中的每个节点，用变量先保存它的上一个节点和下一个节点以免“失联”，然后将它指向上一个节点实现小范围的反转，向后移动一步，再循环

发表于 2021-03-18 23:59:54 回复(0)

Python

JohnLeeTheThird

笔记：python中没有指针或者链表，但是仔细看题就能直到已经给了一个指针的类，然后就是正常的反转链表的思路

# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):#首先给了链表的表头
A = pHead#将表头赋给A变量
if A != None:#记住，若A变量为空，也就没有反转的必要了，直接输出就行
B = pHead.next#在A变量不为空的情况下设置B变量记住下一个的位置
C = A#在最开始的时候在表头的地方直接指向空，就直接变成最后一个节点了
C.next = None
while B != None:#遍历链表，反转，这里的几句话不能随意调换位置，首先是将A指针指向下一个，然后将B指针指向B的下一个，最后，最关键，A的下一个指向C而不是B，然后再将A指针再次赋给C就完成一次循环了。
A = B
B = B.next
A.next = C
C = A
return C
return A
# write code here

发表于 2021-03-17 21:35:18 回复(0)

Python

Treamy

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pre = None
        cur = pHead
        while cur:
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t
        return pre

啪的一下，很快啊！

直接遍历链表，先保存该节点的下一个节点，再让当前的next指向前一个，且让pre指向当前的节点，再让当前指向刚刚保存的，直到遇到为空，返回pre--上一个访问的节点。

发表于 2021-03-16 13:44:08 回复(0)

Python

卢*敏

class Solution:
# 返回ListNode
def ReverseList(self, head):
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev

发表于 2021-03-11 14:17:36 回复(0)

Python

小咕

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        last_num = None 
        
        while pHead is not None:
            last_num,pHead.next,pHead =  pHead,last_num,pHead.next
            
        return last_num

这里要特别注意，

last_num,pHead.next,pHead

这三个变量他们的顺序要有先后，pHead.next 不能在 pHead 后面，不然当pHead先变成了None，那时候就不能给 pHead.next 赋值了

发表于 2021-02-26 01:26:55 回复(0)

Python

食堂在逃干饭王

递归解法，小心点各种边界条件即可

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def __init__(self):
        self.newHead = None
    # 返回ListNode
    def ReverseList(self, pHead):
        if pHead == None:
            return None
        if pHead.next == None:
            return pHead
        # write code here
        if pHead.next.next == None:
            pHead.next.next = pHead
            self.newHead = pHead.next
            pHead.next = None
            return self.newHead
        self.ReverseList(pHead.next)
        pHead.next.next = pHead
        pHead.next = None
        return self.newHead

发表于 2021-01-31 21:05:47 回复(0)

Python

牛客500527307号

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here

        if not pHead:
            return None

        prenode = None                  #新建变量，虚拟的节点，节点的值为None
        while pHead:
            temp = pHead.next           #当前节点的next保存起来
            pHead.next = prenode        #当前节点的next指向当前节点的前一个节点
            prenode = pHead             #把当前节点保存起来
            pHead = temp                #移到下一个节点
        return prenode

编辑于 2021-01-11 21:22:00 回复(0)

Python

惠灵顿靖

# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead == None or pHead.next==None: # 若链表为空或者仅一个数就直接返回
return pHead
pre = None
while(pHead != None):
next = pHead.next # 1
pHead.next = pre # 2
pre = pHead # 3
pHead = next # 4
return pre

public class Solution {
    public ListNode ReverseList(ListNode head) {
      
        if(head==null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
    	ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

编辑于 2021-04-18 21:36:53 回复(1)

Python

牛客182954359号

想复杂了。。。，但也能通过。。。

# -*- coding:utf-8 -*-

# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
cur=pHead
if cur==None:
return None
l=[]
while cur:
l.append(cur.val)
cur = cur.next
l.reverse()
m=[]
for i in range(len(l)):
si=ListNode(l[i])
m.append(si)
for i in range(len(m)-1):
m[i].next=m[i+1]
CUR1=m[0]
return CUR1

发表于 2020-12-24 20:02:14 回复(0)

提交观点

问题信息

链表

来自：寻找时间黑客在线编程大...

难度：

102条回答 5902收藏 335826浏览

通过挑战的用户

查看代码

牛客11552...

2023-03-14 11:22:15
洞洞鞋小公子

2023-03-12 22:30:58
牛客20133...

2023-03-09 16:07:56
松林子木

2023-03-08 10:28:45
牛客17038...

2023-03-07 15:45:53

反转链表

输入

输出

输入

输出

说明

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

迭代版本（python3)：

递归版本（python3)：

代码

思路

初始状态

开始循环前

`p1 = pHead`; `p2 = p1.next`

`pHead.next = None`

第一次循环

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`

第二次循环

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`

第三次循环

第四次循环

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`

补充：特殊情况

问题信息

热门推荐

通过挑战的用户

相关试题

反转链表

输入

输出

输入

输出

说明

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

迭代版本（python3)：

递归版本（python3)：

代码

思路

初始状态

开始循环前

p1 = pHead; p2 = p1.next

pHead.next = None

第一次循环

p3 = p2.next

p2.next = p1

p1 = p2

p2 = p3

第二次循环

p3 = p2.next

p2.next = p1

p1 = p2

p2 = p3

第三次循环

第四次循环

p3 = p2.next

p2.next = p1

p1 = p2

p2 = p3

补充：特殊情况

问题信息

热门推荐

通过挑战的用户

相关试题

`p1 = pHead`; `p2 = p1.next`

`pHead.next = None`

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`

`p3 = p2.next`

`p2.next = p1`

`p1 = p2`

`p2 = p3`