力扣经典150题第六十题：反转链表 II

用户8589624

发布于 2025-11-13 16:17:08

文章被收录于专栏：nginxnginx

标题：使用Java实现反转链表 II

在本文中，我们将解决LeetCode上的第六十题，即反转链表 II。题目要求给定一个单链表的头指针head和两个整数left和right，其中left <= right。我们需要反转从位置left到位置right的链表节点，并返回反转后的链表。

1. 题目分析

题目要求反转链表的一部分，这需要我们找到反转的起始位置和结束位置，然后对这一部分进行反转。同时，我们需要考虑边界情况，如链表为空、left等于right等情况。

2. 解题思路

我们可以使用三个指针来处理这个问题：pre、cur、next。具体步骤如下：

首先，找到left位置的前一个节点pre和left位置的节点cur。
然后，将left位置到right位置的节点反转。
最后，将pre的next指针指向反转后的链表头节点，将反转区间的最后一个节点的next指针指向next节点。

3. Java代码实现

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class ReverseBetween {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) return null;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;

        // 找到left位置的前一个节点pre
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        ListNode next;

        // 反转left到right位置的节点
        for (int i = 0; i < right - left; i++) {
            next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummy.next;
    }
}

4. 测试示例

我们使用几个示例来测试我们的代码：

public class Main {
    public static void main(String[] args) {
        // 示例1
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5;

        ReverseBetween solution = new ReverseBetween();
        ListNode reversedList1 = solution.reverseBetween(node1, 2, 4);
        printList(reversedList1);

        // 示例2
        ListNode node6 = new ListNode(5);
        ListNode reversedList2 = solution.reverseBetween(node6, 1, 1);
        printList(reversedList2);
    }

    public static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}