LeetCode 92. 反转链表 II

问题描述

给你单链表的头指针 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]

提示：

• 链表中节点数目为 n

• 1 <= n <= 500

• -500 <= Node.val <= 500

• 1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

思路

方法一：递归

可以使用递归来反转链表的一部分。首先找到反转的起点，然后递归地反转子链表，最后将子链表连接到原链表中。

方法二：一次遍历

在一次遍历中完成反转操作。使用双指针，分别指向反转部分的前一个节点 pre 和当前节点 cur。然后进行反转操作，最后将反转部分与原链表连接起来。

方法三：单独反转子链表

首先，找到需要反转的子链表的起始节点 leftNode 和结束节点 rightNode，然后将其切断出来。接着，将子链表进行反转，反转后的头节点为 rightNode，尾节点为 leftNode。最后，将反转后的子链表接回到原链表中。

代码实现（Java）

方法一：递归

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        //前进到反转的起点
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    
    //后驱节点
    public ListNode successor = null;
    
    //反转以 head 为起点的 n 个节点，返回新的头节点
    public ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            //记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        //以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        //让反转之后的 head 节点和后面的节点连接起来
        head.next = successor;
        return last;
    }
}

方法二：一次遍历

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        //将 pre 指向第 left 个节点的前一个结点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode next;
        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;
    }
}

方法三：单独反转子链表

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        //将 pre 指向第 left 个节点的前一个结点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode rightNode = pre;
        //将 rightNode 指向 right 节点
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        //切断出一个子链表，其头结点为 leftNode，尾节点为 rightNode
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;
        pre.next = null;
        rightNode.next = null;

        //反转该子链表，反转之后的头节点为 rightNode，尾节点为 leftNode
        reverseLinkedList(leftNode);
        
        //将反转后的子链表接回到原链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummy.next;
    }

    //反转以 head 为头节点的链表
    public void reverseLinkedList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
    }
}

总结

本题提供了多种解题方法，根据需要和题目要求选择合适的方法进行解答。希望这个解题思路对你有所帮助。