问题:

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

解答思路:

以下是使用 Java 实现的反转链表 II 的代码:

class ListNode {
    int val;
    ListNode next;

    ListNode() {}

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

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

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

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }

        ListNode curr = prev.next;
        ListNode next = null;
        for (int i = left; i <= right; i++) {
            next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        // 构建测试链表
        ListNode head = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        int left = 2;
        int right = 4;

        ReverseLinkedListII solution = new ReverseLinkedListII();
        ListNode reversedHead = solution.reverseBetween(head, left, right);

        // 打印反转后的链表
        ListNode curr = reversedHead;
        while (curr!= null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
    }
}


上述代码中,定义了一个'reverseBetween'方法,首先创建一个虚拟头节点'dummy',并将其指向链表的头节点'head'。然后通过一个循环找到需要反转的起始节点'prev'。接下来,从起始节点开始,依次将节点的指针进行反转,直到到达结束节点。最后返回虚拟头节点的下一个节点,即为反转后的链表头。在'main'方法中,构建了一个测试链表,并调用'reverseBetween'方法进行反转并打印结果。

(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)

10-09 10:59