题解 | #链表内指定区间反转#

# class ListNode
#   attr_accessor :val, :next
# 
#   def initialize(val = 0, _next = nil)
#     @val, @next = val, _next
#   end
# end
# 


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution
    def reverseBetween(head, m, n)
        # write code here
        # 虚拟头节点
        vhead = ListNode.new
        vhead.next = head
        pre = vhead
        #找到子序列的前一个结点
        (1...m).each do
            pre = pre.next
        end 
        #找到子序列的最右端
        right = pre
        (m..n).each do
            right = right.next
        end
        #截取子序列
        left = pre.next
        cur = right.next
        #截断子序列
        pre.next = nil
        right.next = nil
        #子序列逆转
        reverseLink(left)
        #重新拼接
        pre.next = right
        left.next = cur

        return vhead.next

    end
    def reverseLink(head)
        cur = head
        pre = nil
        right = nil
        while cur
            right = cur.next
            cur.next = pre
            pre = cur
            cur =right
        end
        return pre
    end
end