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

43个回答

添加回答
推荐
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 回复(40)
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead

        preNode = None
        while pHead:
            # 先保存当前指针的后一个指针
            nextNode = pHead.next
            # 当前指针指向前一个指针
            pHead.next = preNode
            # 当前指针处理完毕,把当前指针和前一个指针后移
            preNode = pHead
            pHead = nextNode

        # 此时pHead为None,pHead的前一个指针指向原链表的最后一个,也就是新链表的第一个
        return preNode
发表于 2019-05-09 11:24:52 回复(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:
            return None
        elif pHead.next==None:
            return pHead
        else:
            front = pHead
            last = front.next
            front.next = None
            while True:
                temp = last.next
                last.next = front
                temp2 = last
                front = last
                last = temp
                if last==None:
                    return temp2
发表于 2019-03-25 16:22:01 回复(0)
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        pre=None
        head=pHead
        while head:
            next=head.next
            head.next=pre
            pre=head
            head=next
        return pre


编辑于 2019-03-22 22:04:33 回复(0)
#         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)