首页 > 试题广场 > 反转链表
[编程题]反转链表
  • 热度指数:796420 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入一个链表,反转链表后,输出新链表的表头。
推荐
public class Solution {
 public static ListNode ReverseList(ListNode head) {
 if(head==null)
 return null;
 ListNode reversedHead=null;
 ListNode current=head;
 ListNode tmp=null;
 ListNode pre=null;
 while(current!=null){
 tmp=current.next;
 current.next=pre;
 if(tmp==null)
 reversedHead=current;
            pre=current;
 current=tmp;
 
 }
 return reversedHead;
 }
}

编辑于 2015-06-19 16:46:40 回复(50)
反转链表三种思路:
1)双指针法:1>初始化两个指针,pre = None,cur = pHead;2>初始化变量tmp存储当前结点;3>两个指针遍历链表,记录当前结点,tmp = cur.next;将当前结点的下一个结点指向当前结点的前一个结点,cur.next = pre;直到链表遍历完,即cur 指向空。4>返回pre
-时间复杂度:O(n)
-空间复杂度:O(1)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def ReverseList(self, pHead):
        if not pHead:
            return pHead
        pre = None
        cur = pHead
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur 
            cur = tmp
        return pre
2)递归求解:1>递归条件:当前结点为空或当前结点的下一个结点为空,返回pHead;2>遍历链表,找到链表最后一个结点;3>当找到链表的最后一个结点后,反转链表,把链表最后一个结点作为头结点,链接前面的结点;4>防止链表循环,执行pHead.next = None;5>返回原链表的最后一个结点
-时间复杂度:O(n)
-空间复杂度:O(1)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def ReverseList(self, pHead):
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        cur = self.ReverseList(pHead.next)
        pHead.next.next = pHead
        pHead.next = None
        return cur
3)辅助栈:利用栈先进后出的性质反转链表。1>初始化栈stack = [];2>将链表结点依次加入栈;3>设反转后链表的头结点为p,p会等于栈顶的结点,设置指针h指向p;4>当stack不为空时,不断stack.pop(),连接每个结点;5>防止链表循环,h.next = None; 6>返回p,得到反转链表。
-时间复杂度:O(n)
-空间复杂度:O(n)
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def ReverseList(self, pHead):
        if not(pHead and pHead.next):
            return pHead
        stack = []
        while pHead:
            stack.append(pHead)
            pHead = pHead.next
        h = stack.pop()
        p = h
        while stack:
            h.next = stack.pop()
            h = h.next
        h.next = None
        return p





发表于 2020-05-25 23:19:36 回复(0)
Python Solution
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        (1151)# write code here
        if not pHead:
            return 
        pre = ListNode(pHead.val)
        cur = pHead.next
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre


发表于 2020-03-21 21:04:01 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        (1151)# write code here
        if pHead == None&nbs***bsp;pHead.next == None:
            return pHead
        leftNode = pHead
        pHead = pHead.next
        leftNode.next = None
        while pHead != None:
            rightNode = pHead
            pHead = pHead.next
            rightNode.next = leftNode
            leftNode = rightNode
        return rightNode

发表于 2020-02-29 23:34:17 回复(0)
# -*- 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
        pre = None
        cur = pHead
        while cur:
            next_Node = cur.next
            cur.next = pre
            pre = cur
            cur = next_Node
        return pre

发表于 2020-01-07 10:29:11 回复(0)
简单易懂Python代码,思路见注释
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        last, crt = None, pHead
        while crt: # 判断crt而非crt.next,防止pHead为None的情况
            next = crt.next # 记录下一个节点的位置
            crt.next = last # 翻转当前节点
            last, crt = crt, next # 访问下一个节点
        return last # 循环结束的条件是crt为None,此时last就是最后一个节点


编辑于 2019-12-31 16:58:37 回复(0)
python Solution:
# -*- 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 = None
        if pHead ==None:return 
        while pHead:
            pre = pHead.next
            pHead.next = last
            last = pHead
            pHead = pre
        return last


发表于 2019-12-07 10:55:43 回复(0)
# -*- 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
        #初始判断,保证链表满足要求,只有pHead就返回它
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        #定义一个空链表
        newlist = None
        while pHead:
            #将链表的Node截断,破坏链表指向关系
            tmp = pHead.next
            #最后的Node指针设为None
            pHead.next = newlist
            #将截断的Node加入到新的last链表
            newlist= pHead
            #将后面的Node给中间变量tmp
            pHead = tmp
        return newlist
            

发表于 2019-12-05 11:35:45 回复(0)
# -*- 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&nbs***bsp;pHead.next is None:
                return pHead
        else:
                cHead = pHead.next
                nHead = cHead.next
                pHead.next = None
                while cHead is not None:
                        cHead.next = pHead
                        pHead = cHead
                        cHead = nHead
                        if cHead is not None:
                                nHead = cHead.next
                return pHead
                        

发表于 2019-12-01 13:01:22 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pre=None
        current=pHead
        pnext=pHead.next
        current.next=pre
        while(pnext!=None):
            pre=current
            current=pnext
            pnext = pnext.next
            current.next=pre
        return current
这个需要设置三个指针,即pre,cureent,next。我们要将pre和current独立出来,同时即把后继变为前驱。使current指向pre,同时要注意的是
current=pnext
pnext = pnext.next
current.next=pre
的顺序不能改,否则会让pnext的的next指向pre,接着就会陷入死循环


发表于 2019-11-05 20:18:00 回复(0)
造一个链表头,每次把取出的原链表的节点接在新链表头的后面
# -*- 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
        head=ListNode(0)
        p=pHead
        while p:
            t=p.next
            p.next=head.next
            head.next=p
            p=t
        return head.next


发表于 2019-10-21 13:28:46 回复(0)

设置3个指针p1, p2, p3,和一个链表a->b->c->d->e->f->g...

本来是p1->p2->p3->d->e->f...,先设置头结点的next是null,变成p1 p2->p3->d->e->f...,然后修改p1<-p2 p3->a->b->c...,然后所有指针都向前走一位变成a<-p1 p2->p3->e->f...
这样一直走到最后一个结点a<-b<-c<-...p1 p2->p3
然后依次修改p2结点的next指向p1,p3结点的next指向p2,就完成了链表的反转。

# -*- 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
        p1 = pHead
        p2 = pHead.next
        p1.next = None
        while p2.next!=None:
            p3 = p2.next
            p2.next = p1
            p1 = p2
            p2 = p3
        p2.next = p1
        return p2
发表于 2019-10-15 19:46:09 回复(0)
# -*- 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
        cur = pHead
        while(cur!=None):
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre
Hint:
循环办法
发表于 2019-10-09 14:47:16 回复(0)
# -*- 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 not pHead or not pHead.next:
            return pHead
        else:
            list1=[]
            node=pHead
            while node:
                list1.append(node.val)
                node=node.next
            list1=list1[::-1]
            res=ListNode(list1[0])
            node1=res
            lenth=len(list1)
            for i in range(1,lenth):
                node1.next=ListNode(list1[i])
                node1=node1.next
            return res
发表于 2019-09-10 14:58:28 回复(0)
两种思路 马克一下
1 非递归 从表头开始反转,直至表尾 (即反转后的原表尾变成表头,原表头变表尾)
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead:
            return None
        tmp=ListNode(0)
        new=pHead
        left=pHead.next
        new.next=None
        while(left):
            tmp=left.next
            left.next=new
            new=left
            left=tmp
             
        return new
2 递归
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead:
            return None
        
        if not pHead.next :
            #ans=pHead
            return pHead
        else:
            
            ans= self.ReverseList(pHead.next)
        pHead.next.next=pHead
        pHead.next=None
        return ans

递归从表头遍历到表尾,然后从表尾到表头反转
发表于 2019-09-06 00:17:04 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        # 判断传入的链表是否为空
        if pHead is None:
            return None
        # 定义空数组承接数值
        attr = []
        p = pHead
        while p is not None:
            attr.append(p.val)
            p = p.next
        # 定义一个新的空表头
        newhead = ListNode(0)  # 一个值为0的节点
        tmp = newhead  # 使用变量
        # 将数组中的数字倒着放到新的链表中
        for i in attr[::-1]:  # 注意,for循环是在数组中
            tmp.next = ListNode(i)  # 将tmp与下一个节点相连
            tmp = tmp.next
        return newhead.next
和之前那到翻转链表的值类似,采用创造新数组的方法,但有个问题是头结点的数值是0,所以最后一行return newhead.next
发表于 2019-08-13 16:48:49 回复(0)
python非递归实现:
def ReverseList(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        newlist=None
        curr=pHead
        while curr:
            temp=curr.next
            curr.next=newlist
            newlist=curr
            curr=temp
        return newlist
递归:
def ReverseList(self, pHead,newlist=None):
        if pHead==None:
            return newlist
        curr=pHead.next
        pHead.next=newlist
        return self.ReverseList(curr,pHead)



编辑于 2019-08-12 11:01:59 回复(0)
# -*- 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
        # 就是正常链表的插入操作,把后面的指针插入到头部
        # 维护两个指针,一个是pHead,来指示下一个想要插入的点
        # 一个是头指针,用来维护被插入的点
        head = ListNode(0)
        head.next = pHead
        if not head.next:
            return pHead
        k = head.next.next
        old = head.next
        while k:
            temp = k.next
            old.next = temp
            k.next = head.next
            head.next = k
            k = temp
        return head.next


编辑于 2019-08-05 10:47:54 回复(0)
 class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        p,q = pHead,None
        while p:
            q,q.next,p = p,q,p.next
        return q 

编辑于 2019-08-01 16:48:56 回复(0)
class Solution:
    """
    如果链表长度 <= 1,则直接返回原头节点
    否则,将原头节点后面的节点依次移动到前面去
    需要操作的只有原头节点后面的节点,然后维护一个新的头节点
    """
    def ReverseList(self, pHead):
        if pHead==None or pHead.next==None:
            return pHead
        head = pHead                # 新的头指针
        while pHead.next:           # 还有节点可以移动
            node = pHead.next       # 即将被移动的节点
            pHead.next = node.next  # 将该节点从后面的链表中删除
            node.next = head        # 移动节点到新的头节点之前
            head = node             # 更新头指针
        return head

发表于 2019-07-26 22:13:47 回复(0)