【Leetcode】92—Reverse Linked List

一、题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度
示例：

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

二、代码实现

首先找到需要反转的链表部分进行反转，反转完毕后连接回去

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if head == None: return head
        dummy = ListNode(-1)
        dummy.next = head
        start = dummy
        for i in range(m-1):
            start = start.next
        
        end = cur = start.next
        pre = None
        for j in range(n-m+1):
            last = cur.next
            cur.next = pre
            pre = cur
            cur = last
        start.next = pre
        end.next = cur

        return dummy.next