首页 > 试题广场 > 反转链表
[编程题]反转链表
输入一个链表,反转链表后,输出新链表的表头。

40个回答

添加回答
推荐
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 回复(39)
#         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
        p = pHead
        q = pHead.next
        p.next = None
        while q:
            r = q.next
            q.next = p
            p = q
            q = r
        return p
            
发表于 2019-03-18 19:45:10 回复(1)
#-- coding:utf-8 --
#class ListNode:
#    def init(self, x):
#        self.val = x
#        self.next = None
class Solution:
    def ReverseList(self, pHead):
    if pHead ==None or pHead.next ==None:#少于两个结点没有反转的必要
        return pHead
    pre = pHead
    now = pHead.next
    pHead.next = None#把当前头结点设为尾节点,尾结点的下一个结点一定指向None(这句写pre.next =None 也可以)
    while now != None:
        tmp = now.next
        now.next = pre
        pre = now
        now = tmp
    return pre#由于退出循环时now一定指向none,则返回now的前一个指针也就是pre作为新的头结点

编辑于 2019-03-15 14:00:07 回复(0)
while True:
    try:
        print '{'+','.join(list(raw_input().strip('{}').split(','))[::-1])+'}'
    except:
        break
Python偷懒一行解决法

发表于 2019-03-15 09:05:37 回复(0)
    
这样为啥就不行呢
def ReverseList(self, pHead):
        # write code here
        res=[]
        while pHead is not None:
            res.append(pHead)
            pHead=pHead.next
        return res[-1]
发表于 2019-03-04 22:07:12 回复(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_node = None
        while pHead != None:
            next_node = pHead.next
            pHead.next = pre_node
            pre_node = pHead
            pHead = next_node
        return pre_node
编辑于 2019-02-08 19:49:54 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None:
            return
        res=[]
        while pHead:
            res.append(pHead)
            pHead = pHead.next
        p_R_Head=res[-1]
        for i in range(len(res)-1, 0, -1):
            res[i].next=res[i-1]
        res[0].next = None
        return p_R_Head

发表于 2019-01-15 19:49:37 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        try:
            tmp = []
            while pHead.next:
                tmp.append(pHead)
                pHead = pHead.next
            tmp.append(pHead)
            tmp.reverse()
            for i in range(len(tmp)-1):
                tmp[i].next = tmp[i+1]
            tmp[-1].next = None
            return tmp[0]
        except:
            return
发表于 2019-01-03 13:43:42 回复(0)

递归递归

class Solution:

# 返回ListNode
def ReverseList(self, pHead):
    if not pHead or not pHead.next:
        return pHead
    head = self.ReverseList(pHead.next)
    node = head
    while node.next:
        node = node.next
    node.next, pHead.next = pHead, None
    return head
发表于 2018-10-01 16:21:51 回复(1)
recursion version, 获得最后两个node。
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        
        if not pHead:
            return
        if pHead.next == None:
            return pHead
        
        i = pHead
        j = pHead.next
        
        while j.next:
            j = j.next # last node
            i = i.next # second last node
        
        i.next = None # == remove last node from node list
        j.next = self.ReverseList(pHead)
        
        return j


发表于 2018-08-03 04:06:44 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        p_next = None
        while pHead:
            _next = pHead.next
            pHead.next = p_next
            p_next = pHead
            pHead = _next
        return p_next
循环判断,两个指针依次向前指,反转对应关系。
发表于 2018-07-03 22:32:22 回复(0)
因为本题 要反转链表那当前节点与后面节点会断掉,因此除了需要记录 前面节点外,还需要记录 后面节点。

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pNode=pHead
        reversed=None
        prev=None
        
        while pNode!=None:
            pNext=pNode.next
        
            if pNext==None:
                reversed=pNode
        
        
            pNode.next=prev
        
            prev=pNode
        
            pNode=pNext
        return reversed
       


发表于 2018-05-11 21:23:55 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        lis = []
        pRes = pHead
        while(pHead):
            lis.append(pHead.val)
            pHead = pHead.next
        lis = lis[::-1]
        p = pRes
        for i in range(len(lis)):
            pRes.val = lis[i]
            pRes = pRes.next
        return p

发表于 2018-05-11 15:38:39 回复(1)
# -*- 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=ListNode(None)
        pre =None
        if pHead==None:
            return None
        
        while pHead!=None:
            last=pHead.next
            pHead.next=pre
            pre=pHead
            pHead=last
        return pre
发表于 2018-05-10 09:40:01 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        head = ListNode(-1)
        while pHead:
            p = pHead.next
            pHead.next = head.next
            head.next = pHead
            pHead = p
        return head.next

#头插法

编辑于 2018-04-23 21:27:07 回复(0)
照着C++的思路写了下python的
class Solution:
    def ReverseList(self, pHead):
        pReverseHead=None
        pNode=pHead
        pPrev=None
        while pNode!=None:
            pNext=pNode.next
            if pNext==None:
                pReverseHead=pNode
            pNode.next=pPrev
            pPrev=pNode
            pNode=pNext
        return pReverseHead

发表于 2018-04-15 20:14:15 回复(0)
注意是反转链表,并返回反转后的链表的首节点,而不仅仅是返回输出的值。链表注意边界的问题,在我的代码里,循环那儿处理不了最后一个节点,所以我在循环结束之后,单独处理了最后一个节点。
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:
            return None
        #如果输入的链表只有一个节点,返回这个节点
        if pHead.next == None:
            return pHead
        #当链表的节点个数>=2的时候进入到下面的循环中
        node = pHead
        last = None
        while node.next != None:
            #把当前节点的对下一个节点的引用保存下来
            tmp = node.next
            #当前节点的引用指向上一个节点
            node.next = last
            #在下一轮之前,把当前节点复制给last
            last = node
            #进入下一个节点
            node = tmp
        #当node等于倒数第二个节点的时候,node.next 就是最后一个节点,此时进入不了
               #循环,所以把最后一个节点的引用赋值给倒数第二个节点
               node.next = last
        return node

if __name__ == "__main__":
    node_6 = ListNode(13)
    node_5 = ListNode(11)
    node_4 = ListNode(7)
    node_3 = ListNode(5)
    node_2 = ListNode(3)
    head = ListNode(2)
    
    head.next = node_2
    node_2.next = node_3
    node_3.next = node_4
    node_4.next = node_5
    node_5.next = node_6
    
    solution = Solution()
    result = solution.ReverseList(head)
    print(result.val)

发表于 2018-03-25 15:53:43 回复(0)
思路:当链表为空或者只有一个元素时,返回原链表。否则使用尾插法将原链表的元素建立反转链表
具体为定义反转链表的头指针last,当原列表不空的时候,使用中间变量保存原链表指向第二个节点
的指针(tmp = pHead.next),将原链表头节点指向反转列表的头结点(pHead = last),更新反转
链表的头结点(last=pHead),更新原链表的头结点,指向原链表的第二个指针(pHead = tmp)  
最后返回反转列表的头指针
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        #链表为空,或者只有一个元素,返回原列表
        if  not pHead or not pHead.next:
            return pHead
        # last为反转链表的头指针
        last = None
        while pHead:
            # 保存原链表指向第二个节点的指针
            tmp = pHead.next
            # 将头结点的的下一个指针指向反转链表
            pHead.next = last
            # 反转链表的头指针更新
            last = pHead
            # 更新原链表头指针
            pHead = tmp
        return last

编辑于 2018-03-25 14:46:33 回复(0)

def ReverseList(self, pHead):

    # write code here
    if pHead is None or pHead.next is None:
        return pHead

    head = None
    while pHead:
        '预存下一个节点防止链表断裂找不到下一个位置'
        temp = pHead.next
        '反转当前结点'
        pHead.next = head
        '新的头节点'
        head = pHead
        '移动到预存的下一个节点继续重复上述步骤'
        pHead = temp
    return head
发表于 2018-03-18 14:59:30 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号