题目描述

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

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

示例

示例 1：

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

解答方法

方法一:迭代

思路

找到要翻转部分的链表,将其翻转,再与原链表拼接;

代码

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
# 找到翻转链表部分的前一个节点, 1->2->3->4->5->NULL, m = 2, n = 4 指的是 节点值为1
        for i in range(m-1):
            pre = pre.next
# 用双指针,进行链表翻转
        cur = pre.next
        head = None
        for i in range(n-m+1):
            tmp = cur.next
            cur.next = head
            head = cur
            cur = tmp
# 将翻转部分 和 原链表拼接
        pre.next.next = cur
        pre.next = head
        return dummy.next

时间复杂度

空间复杂度

提交结果

Runtime: 32 ms, faster than 93.47% of Python3 online submissions for Reverse Linked List II.
Memory Usage: 13.9 MB, less than 7.41% of Python3 online submissions for Reverse Linked List II.