golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2022-11-24 11:02:29

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseLinkedList(head *ListNode) {
    var pre *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
}

func reverseBetween(head *ListNode, left, right int) *ListNode {
    // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
    dummyNode := &ListNode{Val: -1}
    dummyNode.Next = head

    pre := dummyNode
    // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
    // 建议写在 for 循环里，语义清晰
    for i := 0; i < left-1; i++ {
        pre = pre.Next
    }

    // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
    rightNode := pre
    for i := 0; i < right-left+1; i++ {
        rightNode = rightNode.Next
    }

    // 第 3 步：切断出一个子链表（截取链表）
    leftNode := pre.Next
    curr := rightNode.Next

    // 注意：切断链接
    pre.Next = nil
    rightNode.Next = nil

    // 第 4 步：同第 206 题，反转链表的子区间
    reverseLinkedList(leftNode)

    // 第 5 步：接回到原来的链表中
    pre.Next = rightNode
    leftNode.Next = curr
    return dummyNode.Next
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-24 11:01:58

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left, right int) *ListNode {
    // 设置 dummyNode 是这一类问题的一般做法
    dummyNode := &ListNode{Val: -1}
    dummyNode.Next = head
    pre := dummyNode
    for i := 0; i < left-1; i++ {
        pre = pre.Next
    }
    cur := pre.Next
    for i := 0; i < right-left; i++ {
        next := cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummyNode.Next
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15 MB, 提交时间: 2022-11-24 11:01:36

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # 设置 dummyNode 是这一类问题的一般做法
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next

        cur = pre.next
        for _ in range(right - left):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy_node.next

python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-24 11:00:29

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverse_linked_list(head: ListNode):
            # 也可以使用递归反转一个链表
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next

        # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        # 建议写在 for 循环里，语义清晰
        for _ in range(left - 1):
            pre = pre.next

        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        curr = right_node.next

        # 注意：切断链接
        pre.next = None
        right_node.next = None

        # 第 4 步：同第 206 题，反转链表的子区间
        reverse_linked_list(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return dummy_node.next