链表指定区间反转

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

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

输出：1->4->3->2->5->NULL

头插法

Java实现

    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next; //注意此处，为啥不能用cur
            pre.next = next;
        }
        return dummyNode.next;
    }

python实现

    def reverseBetween2(self, head, left, right):
        # 设置 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

穿针引线法

Java实现

    public static ListNode reverseListNode(ListNode head, int left, int right) {
        //特殊情况考虑
        if(head == null || head.next == null || left == right){
            return head;
        }
        //建立虚拟节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode temp = dummyNode;
        int count =0;
        //找到left前一个节点
        for(;count < left-1;count++){
            temp = temp.next;
        }

        //反转链表开始的位置
        ListNode leftNode = temp.next;
        //记录反转后链表的头节点
        ListNode rightNode = null;
        ListNode next = null;

        //开始反转链表
        for(;count<right;count++){
            next = leftNode.next;
            leftNode.next = rightNode;
            rightNode = leftNode;
            leftNode = next;
        }

        ListNode curRight = rightNode;
        //遍历到链表的尾部
        while (curRight.next != null){
            curRight = curRight.next;
        }
        //让反转区间和区间后面的位置相连接
        curRight.next = leftNode;
        //让区间前面的和反转区间相连接
        temp.next = rightNode;
        return dummyNode.next;
    }

python实现

    def reverseBetween(self, head, left, right):
        def reverse_linked_list(head):
            # 也可以使用递归反转一个链表
            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 步：反转链表的子区间
        reverse_linked_list(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return dummy_node.next