【算法设计与分析】反转链表 ||

       📝个人主页：五敷有你      

 🔥系列专栏：算法分析与设计

⛺️稳中求进，晒太阳

题目

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

示例

示例 1：

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

示例 2：

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

思路（虚拟头节点）

1. 创建一个虚拟节点 dummy，并将其 next 指向 head，这样做是为了简化边界情况的处理。
2. 找到左边界的前一个节点 prev。遍历链表，移动 prev 指针到第 left - 1 个节点处。
3. 从 prev 开始，遍历链表直到达到右边界的位置 right。
4. 在遍历过程中，依次将当前节点的 next 指针指向其后继节点的后继节点（即跳过当前节点的后继节点），然后将后继节点连接到 prev 节点后面。重复这一过程直到完成 left 到 right 区间的节点逆序。
5. 返回虚拟节点 dummy 的 next 指针，即为反转后的链表头节点。

代码实现

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedListBetween {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) {
            return head;
        }
        
        // 使用虚拟节点来简化操作
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        // 找到左边界的前一个节点
        ListNode prevLeft = dummy;
        for (int i = 1; i < left; i++) {
            prevLeft = prevLeft.next;
        }
        
        // 开始头插法反转
        ListNode current = prevLeft.next;
        for (int i = left; i < right; i++) {
            ListNode next = current.next;
            current.next = next.next;
            next.next = prevLeft.next;
            prevLeft.next = next;
        }
        
        return dummy.next;
    }
}

运行结果