92.反转链表2.md

92. 反转链表 II

url

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
输入：head = [5], left = 1, right = 1
输出：[5]

方法

code

js

let reverseBetween = (head, m, n) => {
    let p = head;
    let idx = 1;
    let stack = [];
    while (p != null) {
        if (idx >= m && idx <= n)
            stack.push(p.val)
        idx++
        p = p.next;
    }
    idx = 1;
    p = head;
    while (p != null) {
        if (idx >= m && idx <= n)
            p.val = stack.pop();
        idx++;
        p = p.next;
    }
    return head;
}

go

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    pre, cur, next := dummy, &ListNode{}, &ListNode{}
    for i := 1; i < m; i++ {
        pre = pre.Next
    }
    cur = pre.Next
    for i := m; i < n; i++ {
        next = cur.Next
        cur.Next = next.Next
        next.Next = pre.Next
        pre.Next = next
    }
    return dummy.Next
}

java

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode p = head;
        int idx = 1;
        Stack<Integer> stack = new Stack<>();
        while (p != null) {
            if (idx >= m && idx <= n)
                stack.push(p.val);
            idx++;
            p = p.next;
        }
        idx = 1;
        p = head;
        while (p != null) {
            if (idx >= m && idx <= n)
                p.val = stack.pop();
            idx++;
            p = p.next;
        }
        return head;
    }
}