92. 反转链表 II--🀄️

categories: [Blog,Algorithm]

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) {
            ListNode tempNext = temp.next;
            if (index < m) {
                prev = temp;
            }
            if (index == m) {
                tail = temp;
            }
            if (index >= m) {
                temp.next = newNode;
                newNode = temp;
            }
            index++;
            temp = tempNext;
        }
        tail.next = temp;
        prev.next = newNode;
        return guard.next;
    }