LeetCode 92. 反转链表 II

作者: 陈陈chen | 来源:发表于2021-09-08 18:15 被阅读0次

2.链表（二）
递归反转链表的一部分
算法学习（链表相关问题）
Leetcode日记：92&206.反转链表
LeetCode 92. 反转链表 II
每日一题1-反转链表 II
链表中间段逆序
LeetCode 92. 反转链表 II
leetcode 92. 反转链表 II
LeetCode 92. 反转链表 II

1、题目

image.png

2、分析

思路一：
1、把链表中的正整数都保存到一个数组中。后面直接用数组中的值来重新构造链表
2、left前面的元素不变，直接构造链表
3、left和right中的元素，从right - 1的元素开始往前构造到left - 1
4、right后面的元素不变，直接构造链表

思路二：

image.png

1、记录下反转段链表的前一个节点pre和后一个节点succ。找到left和right节点
2、将待反转链表反转
3、将反转后的链表，跟pre和succ拼接起来

思路三：
使用递归的方法。但是递归的方法比较难以理解。

3、代码

思路一代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        
        //先把链表中的值，保存到数组中
        List<ListNode> arry = new ArrayList<ListNode>();
        while(head != null)
        {
            arry.add(head);
            head = head.next;
        }
        ListNode res = new ListNode();
        ListNode cur = null;
        //从0开始，到left - 2个元素，不用反转，直接构造
        for (int i = 0; i < left - 1; i++){
                ListNode tmp = arry.get(i);
                if(cur == null)
                {
                    cur = tmp;
                    res = tmp;
                }
                cur.next = tmp;
                cur = tmp;
            }
        //从right - 1开始，往前遍历数组，一直到left - 1个元素为止，构造链表。这里就是反转的链表了
        for (int i = right - 1; i >= left - 1; i--){
                ListNode tmp = arry.get(i);
                if(cur == null)
                {
                    cur = tmp;
                    res = tmp;
                }
                cur.next = tmp;
                cur = tmp;
        }
        //从right元素开始，不用反转，直接构造到最后一个
        for (int i = right; i < arry.size(); i++){
                ListNode tmp = arry.get(i);
                if(cur == null)
                {
                    cur = tmp;
                    res = tmp;
                }
                cur.next = tmp;
                cur = tmp;
        }
        cur.next = null;

        return res;
    }
}

思路二代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //构造一个虚拟节点，这样就不用特殊处理left = 1的情况
        ListNode fakeNode = new ListNode(-1);
        fakeNode.next = head;
        ListNode pre = fakeNode;

        //找到pre节点
        for(int i = 0; i < left - 1; i++){
            pre = pre.next;
        }
        ListNode leftNode = pre.next;
        //找到succ节点
        ListNode succ = leftNode;
        for(int i = 0; i < right - left; i++){
            succ = succ.next;
        }
        //反转链表
        ListNode rightNode = succ;
        succ = succ.next;
        rightNode.next = null;
        reverseLinkedList(leftNode);
        //拼接链表
        pre.next = rightNode;
        leftNode.next = succ;
        return fakeNode.next;
    }
    //反转链表函数
    private void reverseLinkedList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    } 
}