92-反转链表

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

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

---

示例

输入: 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
        # 找到翻转链表部分的前一个节点
        for _ in range(m-1):
            pre = pre.next
        # print("pre:", pre.val)
        rear1 = pre # 翻转部分的前一个结点
        rear2 = pre.next # 翻转部分的第一个结点，翻转后为尾结点
        cur_node = pre.next
        # 翻转部分的头结点
        dummy2 = ListNode(-1)
        for _ in range(n-m+1):
            # 头插法翻转链表
            save_node = cur_node.next
            cur_node.next = dummy2.next
            dummy2.next = cur_node
            cur_node = save_node
        # 拼接
        rear2.next = cur_node
        rear1.next = dummy2.next
        # head结点可能已经改变，返回头结点的下一节点
        return dummy.next

---

相关信息

LeetCode：Discussion | Solution