目录

一、题目内容

二、解题思路

三、代码

一、题目内容

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

二、解题思路

与leetcode_206. 反转链表不同的是起始位置和结束位置的确定，那么需要额外记录反转链表区域前的节点和反转链表区域后的节点位置，然后反转链表，最后连接之前存储的区域前和区域后的节点即可。

三、代码

  

   

    

     

    
    

     

      # 2020-10-23
     
    
   

    

     

    
    

     

      # 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 reverseBetween(self, head, m, n):
     
    
   

    

     

    
    

     
 """
     
    
   

    

     

    
    

     

       :type head: ListNode
     
    
   

    

     

    
    

     

       :type m: int
     
    
   

    

     

    
    

     

       :type n: int
     
    
   

    

     

    
    

     

       :rtype: ListNode
     
    
   

    

     

    
    

     

       """
     
    
   

    

     

    
    

     
 # 1 --> 2 --> 3 --> 4 --> 5 --> null m = 2, n = 4
     
    
   

    

     

    
    

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

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 # pre:1 post:5 h:2 t:4
     
    
   

    

     

    
    

     
 # reverseList:反转链表
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       dummy = ListNode(None)
     
    
   

    

     

    
    

     

       dummy.next = head
     
    
   

    

     

    
    

     

       before_reverse_start = dummy
     
    
   

    

     

    
    

     
 for _ in range(m - 1):
     
    
   

    

     

    
    

     

       before_reverse_start = before_reverse_start.next
     
    
   

    

     

    
    

     

       reverse_head = before_reverse_start.next
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       end = reverse_head
     
    
   

    

     

    
    

     
 for _ in range(n - m):
     
    
   

    

     

    
    

     

       end = end.next
     
    
   

    

     

    
    

     

       reversed_list_next = end.next
     
    
   

    

     

    
    

     

       end.next = None
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def reverseList(head):
     
    
   

    

     

    
    

     
 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
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       before_reverse_start.next = reverseList(reverse_head)
     
    
   

    

     

    
    

     

       reverse_head.next = reversed_list_next
     
    
   

    

     

    
    

     
 return dummy.next
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       head = ListNode(1)
     
    
   

    

     

    
    

     

       head.next = ListNode(2)
     
    
   

    

     

    
    

     

       head.next.next = ListNode(3)
     
    
   

    

     

    
    

     

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

    

     

    
    

     

       head.next.next.next.next = ListNode(5)
     
    
   

    

     

    
    

     

       m, n = 2, 4
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.reverseBetween(head, m, n)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

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

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