92. 反转链表 II--🀄️

92. 反转链表 II

难度中等 690

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

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

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

输出: 1->4->3->2->5->NULL。

todo

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dmy = new ListNode(0);
        dmy.next = head;
        int delta = n-m;
        ListNode pre = dmy,tail = head;
        //先定位出m节点和m之前的节点
        while(m>1){
            pre = tail;
            tail = tail.next;
            m--;
        }
        while(delta > 0){
            ListNode next = tail.next;
            tail.next = next.next;//tail一直不变，只要修改指针到next.next
            next.next = pre.next;//next.next指向pre的next，也就是最新的第m个位置
            pre.next = next;//更新next为最新的第m个位置
            delta --;
        }

        return dmy.next;
    }

---

todo

    //3段合并
    public ListNode reverseBetween1(ListNode head, int m, int n) {
        if (head == null || m == n) {
            return head;
        }
        ListNode guard = new ListNode(-1);
        guard.next = head;
        ListNode temp = guard;
        ListNode prev = guard;
        ListNode newNode = null;
        ListNode tail = null;
        int index = 0;
        while (temp != null && index <= n) &#123;
            ListNode tempNext = temp.next;
            if (index < m) &#123;
                prev = temp;
            &#125;
            if (index == m) &#123;
                tail = temp;
            &#125;
            if (index >= m) &#123;
                temp.next = newNode;
                newNode = temp;
            &#125;
            index++;
            temp = tempNext;
        &#125;
        tail.next = temp;
        prev.next = newNode;
        return guard.next;
    &#125;