牛客网高频算法题系列-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$
置信保持的力量！