Reverse a linked list from position m to n. Do it in one-pass.

　　Note: 1 ≤ m ≤ n ≤ length of list.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

思路
　　这到题目和之前的做的链表反转使一样，只不过这里因为是对链表中部分进行反转，所以需要处理的细节稍微会多一些。不过总体来说不是很难。时间复杂度为O(n), 空间复杂度为O(1)。详细参考图示和代码
图示
 【LeetCode每天一题】Reverse Linked List II(旋转链表II) 随笔
解决代码
  

 1 # Definition for singly-linked list.
 2 # class ListNode(object):
 3 # def __init__(self, x):
 4 # self.val = x
 5 # self.next = None
 6 
 7 class Solution(object):  8     def reverseBetween(self, head, m, n):  9         """
10  :type head: ListNode 11  :type m: int 12  :type n: int 13  :rtype: ListNode 14         """
15         res = ListNode(0) # 使用哨兵节点，简化代码 16         first, res.next, count = res, head, n-m # 这里使用count变量来记录应该节点的次数 18         while m > 1: # 找到开始反转节点的前一个节点。 19             first = first.next 20             m-= 1
21             
22         re = one = first.next # first.next 为开始反转的节点 23         tem = None # 辅助节点 24         while one and count >= 0: # 将需要反转节点的部分进行反转。 25             t = one.next 26             one.next = tem 27             tem = one 28             one = t 29             count -= 1
30         
31         first.next = tem # 将节点的首位连上 32         re.next = one 33         return res.next # 返回结果 34         
  

 

 
 




    

        

            

                

                    

                        
                    

                    

                        

                            扫码关注我们
                        

                        

                            微信号：SRE实战
                        

                        

                            拒绝背锅 运筹帷幄