Java 反转部分单向链表

Question

可以使用迭代的方式来反转部分单向链表。

具体步骤如下：

1. 首先，根据给定的起始位置和结束位置，找到需要反转的起始节点 startNode 和结束节点 endNode ，以及它们前面的节点 prevStartNode 和 prevEndNode 。
2. 定义两个指针变量 prev 和 current ，分别指向 startNode 和 endNode 。
3. 进行反转操作，将 current 指向节点的 next 指针指向前一个节点 prev 。然后将 prev 和 current 都往后移动一位。
4. 重复步骤 3，直到 current 指向 endNode ，完成反转操作。
5. 最后，将 prevStartNode 的 next 指针指向 endNode ，将 startNode 的 next 指针指向 prevEndNode 。

下面是对应的 Java 代码实现：

public class ListNode {
    int val;
    ListNode next;

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

public class ReversePartialLinkedList {
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        // 使用一个 dummy 节点方便处理边界情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 找到需要反转的起始节点和结束节点，以及它们的前面节点
        ListNode prevStartNode = dummy;
        ListNode prevEndNode;
        for (int i = 1; i < m; i++) {
            prevStartNode = prevStartNode.next;
        }
        ListNode startNode = prevStartNode.next;
        ListNode current = startNode;
        for (int i = m; i < n; i++) {
            current = current.next;
        }
        ListNode endNode = current;
        prevEndNode = current.next;

        // 反转操作
        ListNode prev = null;
        current = startNode;
        while (current != endNode) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        current.next = prev;

        // 重新连接反转后的链表
        prevStartNode.next = endNode;
        startNode.next = prevEndNode;

        // 返回头节点
        return dummy.next;
    }

    public static void main(String[] args) {
        // 创建一个示例链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 反转链表的第 2 个节点到第 4 个节点（包括第 2 个和第 4 个节点）
        ListNode reversed = reverseBetween(head, 2, 4);

        // 输出反转后的链表：1 -> 4 -> 3 -> 2 -> 5
        ListNode node = reversed;
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.println("null");
    }
}

以上代码会输出：

1 -> 4 -> 3 -> 2 -> 5 -> null

即将原链表的第 2 个节点到第 4 个节点部分反转后的结果。