LeetCode 92. 反转链表 II(Reverse Linked List II)

92. 反转链表 II
92. Reverse Linked List II

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

说明:
1 ≤ m ≤ n ≤ 链表长度。

LeetCode92. Reverse Linked List II中等

示例:

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

Java 实现

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return val + "->" + next;
    }
}

import java.util.Stack;

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        Stack<Integer> stack = new Stack<>();
        int i = 1;
        while (head != null) {
            if (i < m) {
                tail.next = head;
                tail = tail.next;
            } else if (i >= m && i <= n) {
                stack.push(head.val);
            } else if (i > n) {
                break;
            }
            head = head.next;
            i++;
        }
        while (!stack.isEmpty()) {
            tail.next = new ListNode(stack.pop());
            tail = tail.next;
        }
        tail.next = head;
        return dummy.next;
    }
}

相似题目

• 206. 反转链表 Reverse Linked List

参考资料

• https://leetcode.com/problems/reverse-linked-list-ii/
• https://leetcode-cn.com/problems/reverse-linked-list-ii/