关于java:牛客网高频算法题系列BM2链表内指定区间反转

牛客网高频算法题系列 -BM2- 链表内指定区间反转

题目形容

将一个节点数为 size 链表 m 地位到 n 地位之间的区间反转，要求工夫复杂度 O(n)，空间复杂度 O(1)。

原题目见：BM2 链表内指定区间反转

解法一：链表遍历，指针替换

因为起始地位可能是头结点，所以首先设置一个虚构的头结点 dummyNode 并将 next 指向原有的头结点，而后处理过程如下：

• 首先遍历链表，找到起始地位 m 的前一个结点 pre，用来记录反转前的结点；
• 而后用 cur 和 next 记录 pre 的 next 结点，用 next 记录 cur 的 next 结点；
• 而后持续遍历链表，通过替换 pre、next、cur 的 next 指针，将 next 结点转到 pre 结点的下一个结点处，而后循环解决 cur 的下一个结点；
• 遍历到完结完结地位 n 的结点即反转完结。
• 最初，返回 dummyNode 结点的 next 结点即为反转后的链表。

public class Bm002 {
    /**
     * @param head ListNode 类
     * @param m    起始地位
     * @param n    完结地位
     * @return ListNode 类
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {if (head == null || head.next == null) {return head;}
        if (m == n) {return head;}
        // 设置虚构头结点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // pre 为反转区间的前一个结点
        ListNode pre = dummyNode;
        for (int i = 0; i < m - 1; i++) {pre = pre.next;}
        // cur 初始为反转区间的起始结点
        ListNode cur = pre.next;
        ListNode next;
        for (int i = 0; i < n - m; i++) {
            // 通过替换 next 指针指向，将 next 结点转到 pre 结点的下一个结点处
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        // 最初，返回 dummyNode 结点的 next 结点即为反转后的链表
        return dummyNode.next;
    }

    public static void main(String[] args) {ListNode head = ListNode.testCase2();
        System.out.println("指定区间反转之前");
        ListNode.print(head);

        ListNode newHead = reverseBetween(head, 2, 4);
        System.out.println("指定区间反转之后");
        ListNode.print(newHead);
    }
}

$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量！