目录

一、题目内容

二、解题思路

三、代码

一、题目内容

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

二、解题思路

每次记录原始节点的next节点，然后将原始节点和新的下一个节点（一开始为Null）进行连接，之后新的下一个节点变为原始节点，原始节点变为原始节点的next的节点，再重复这样的操作，直到原始节点为Null停止循环。

三、代码

  

   

    

     

    
    

     

      # Definition for singly-linked list.
     
    
   

    

     

    
    

     

      class ListNode:
     
    
   

    

     

    
    

     
 def __init__(self, x):
     
    
   

    

     

    
    

     

       self.val = x
     
    
   

    

     

    
    

     

       self.next = None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def __repr__(self):
     
    
   

    

     

    
    

     
 return str(self.val)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def reverseList(self, head: ListNode):
     
    
   

    

     

    
    

     
 # null 1 --> 2 --> 3 --> 4 --> null
     
    
   

    

     

    
    

     
 # null <-- 1 <-- 2 <-- 3 <-- 4 null
     
    
   

    

     

    
    

     
 if not head:
     
    
   

    

     

    
    

     
 return None
     
    
   

    

     

    
    

     

       cur, cur_new_next = head, None
     
    
   

    

     

    
    

     
 while cur:
     
    
   

    

     

    
    

     
 # save original next node
     
    
   

    

     

    
    

     

       origin_next = cur.next
     
    
   

    

     

    
    

     
 # link new next node
     
    
   

    

     

    
    

     

       cur.next = cur_new_next
     
    
   

    

     

    
    

     
 # current node turns to new next node
     
    
   

    

     

    
    

     

       cur_new_next = cur
     
    
   

    

     

    
    

     
 # original next node turns to current node
     
    
   

    

     

    
    

     

       cur = origin_next
     
    
   

    

     

    
    

     
 return cur_new_next
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       head = ListNode(1)
     
    
   

    

     

    
    

     

       head.next = ListNode(2)
     
    
   

    

     

    
    

     

       head.next.next = ListNode(3)
     
    
   

    

     

    
    

     

       head.next.next.next = ListNode(4)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.reverseList(head)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110226074