LeetCode92. 反转链表 II🌟🌟🌟中等

算法系统课免费

课后作业

问题描述

原文链接：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

代码实现

Java

/**
 * 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 {

    ListNode last = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
    //left = 1
        if(left == 1){
            return reverseThN(head, right);
        }
        //1~left - 1
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    // 反转第1～n的节点
    ListNode reverseThN(ListNode head, int n){
        if(n == 1){
            last = head.next;
            return head;
        }

        ListNode newHead = reverseThN(head.next, n - 1);
        head.next.next = head;
        head.next = last;
        return newHead;
    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    last = None

    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        if left == 1:
            return self.reverseThN(head, right)

        head.next = self.reverseBetween(head.next, left - 1, right - 1)
        return head

    def reverseThN(self, head, n):
        if n == 1:
            self.last = head.next
            return head

        newHead = self.reverseThN(head.next, n - 1)
        head.next.next = head
        head.next = self.last
        return newHead

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
private:
    ListNode* last = nullptr;

public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == 1) {
            return reverseThN(head, right);
        }
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }

    ListNode* reverseThN(ListNode* head, int n) {
        if (n == 1) {
            last = head->next;
            return head;
        }

        ListNode* newHead = reverseThN(head->next, n - 1);
        head->next->next = head;
        head->next = last;
        return newHead;
    }
};

Go

发表回复取消回复

后才能评论

我来吃饭啦永久会员 2024年6月20日上午9:53

打卡

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        p0 = dummy = ListNode(next=head)
        for _ in range(left - 1):
            p0 = p0.next

        pre = None
        cur = p0.next
        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre  # 每次循环只修改一个 next，方便大家理解
            pre = cur
            cur = nxt

        # 见视频
        p0.next.next = cur
        p0.next = pre
        return dummy.next

先化为前right项，再让left逐渐为1，采用递归的思想

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    last = None
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == 1:
            return self.reversethN(head,right)

        head.next = self.reverseBetween(head.next,left-1,right-1)
        return head

    def reversethN(self,head,n):
        if n == 1:
            self.last = head.next
            return head

        newhead = self.reversethN(head.next,n-1)
        head.next.next = head
        head.next = self.last
        return newhead

Mr.肖永久会员 2024年3月26日下午3:20

没有采用递归erverseBetweeen，
直接通过left定位到要反转的起始位置
将反转后的链表接起来

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {

        int n = right - left + 1;

        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;

        for(int i = 1; i < left; i++){
            pre = pre.next;
            cur = cur.next;
        }

        pre.next = reverseFN(cur,n);
        return dummy.next;

    }

    //反转位置1～n的结点的链表，返回反转之后的链表
    ListNode last = null;
    private ListNode reverseFN(ListNode head,int n){

        // if(head == null){
        //     return head;
        // }

        if(n == 1){
            last = head.next;
            return head;
        }

        ListNode newHead = reverseFN(head.next,n-1);
        head.next.next = head;
        head.next = last;

        return newHead;
    }
}

少年不识流川枫永久会员 2024年2月27日下午8:32

打卡

class Solution {
    ListNode last = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //结束条件
        if(right == 1){
            last = head.next;
            return head;
        }

        //等价关系式，这里分两种情况，left=1 或者left！=1， right随意
        if(left == 1){
            return reverseFirst(head,right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;  
    }

    //反转前1~n的链表，后面不动
    public ListNode reverseFirst(ListNode head, int right){
        //结束条件
        if(right == 1){
            last = head.next;
            return head;
        }
        //等价关系式
        ListNode newListNode = reverseFirst(head.next,right - 1);
        head.next.next = head;
        head.next = last;

        return newListNode;
    }

}

结束条件right 1，，，不能是head.next null
并且自己漏了last = head.next;

Yuki 永久会员 2024年1月31日上午9:01

写错了，明天再写一遍
class Solution {
private:
void reverseLinkedlist(ListNode*head){

    ListNode*pre=nullptr;
    ListNode*cur=head;

    while(cur!=nullptr){
        ListNode*tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }

}

public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode*dummyHead=new ListNode(0);
dummyHead->next=head;

    ListNode*pre=dummyHead;
    ListNode*rightNode=dummyHead;

    //确定几个位置
    left=left-1;
    while(left--){
        pre=pre->next;
    }
    ListNode*leftNode=pre->next;

    while(right--){
        rightNode=rightNode->next;
    }
    ListNode*tmp=rightNode->next;

    //切断链表
    pre->next=nullptr;
    rightNode->next=nullptr;

    //翻转链表
    reverseLinkedlist(leftNode);

    //链表拼接回去
    pre->next=rightNode;
    leftNode->next=tmp;

    return dummyHead->next;
}

};

Yuki 永久会员 2024年1月30日下午2:18

打卡，递归法二刷再看

class Solution {
private:
//翻转链表
void reverseLinkedList(ListNodehead){
ListNodepre=nullptr;
ListNode*cur=head;

    while(cur!=nullptr){
        ListNode*tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }
}

public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode*dummyHead=new ListNode(0);
dummyHead->next=head;

    ListNode*pre=dummyHead;
    ListNode*cur=dummyHead;

    //找节点左右边界
    left=left-1;

    while(left--){
        pre=pre->next;
    }
    while(right--){
        cur=cur->next;
    }

    //截出一个链条，并切断链接
    ListNode*leftNode=pre->next;
    ListNode*rightNode=cur;
    cur=cur->next;

    pre->next=nullptr;
    rightNode->next=nullptr;

    reverseLinkedList(leftNode);

    //把链表接回来
    pre->next=rightNode;
    leftNode->next=cur;

    return dummyHead->next;
}

};

uu 永久会员 2023年9月20日上午10:02

/**
 * 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; }
 * }
 */

// 【思路】递归处理
// 时间复杂度：O(n)
// 空间复杂度：O(n)
// class Solution {
//     ListNode res = null;

//     public ListNode reverseBetween(ListNode head, int left, int right) {
//         //函数目的：反转left-right

//         //结束条件
//         if(left == 1) {
//             return reverseList(head, right);
//         }
//         //关系式
//         else {
//             head.next = reverseBetween(head.next, left - 1, right - 1);
//             return head;
//         }

//     }

//     ListNode reverseList(ListNode head, int n) {
//         //函数目的：反转1-n位

//         //结束条件
//         if(n == 1) {
//             res = head.next;
//             return head;
//         }
//         //关系式
//         ListNode newHead = reverseList(head.next, --n);
//         head.next.next = head;
//         head.next = res;
//         return newHead;
//     }
// }

//【思路】头插法-穿针引线
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        int diff = right - left;
        ListNode pre = dummyNode;

        if(diff < 1) {
            return head;
        }

        //找到pre
        while(left > 1) {
            pre = pre.next;
            left--;
        }
        //找到suc
        ListNode suc = pre.next;

        while(diff > 0) {
            ListNode nxt = suc.next;
            suc.next = nxt.next;
            nxt.next = pre.next;
            pre.next = nxt;
            diff--;
        }
        return dummyNode.next;
    }
}

泡芙永久会员 2023年9月4日下午4:50

递归

Time：O(n)
Space：O(n)

class Solution {
    ListNode last = null;
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 相当于反转前 n 个元素
            return reverseN(head, right);
        }

        // 1~left-1不需要反转
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    // 反转第1~n的节点
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            last = head.next;// 记录第 n + 1 个节点
            return head;
        }

        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = last;
        return newHead;
    }
}

AD钙奶普通 2023年8月31日上午12:13

原地反转

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

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

        ListNode pre = dummyHead;
        ListNode cur = head;
        for(int i = 0; i < left - 1; i ++) {
            cur = cur.next;
            pre = pre.next;
        }
        for(int i = left; i < right; i ++) {
            ListNode tmp = cur.next;
            cur.next = tmp.next;
            tmp.next = pre.next;
            pre.next = tmp;
        }

        return dummyHead.next;
    }
}

阿尚普通 2023年8月17日下午1:43

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // base case
        if (left == 1) {
            return reverseN(head, right);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode successor = null; // 后驱节点
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    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;

    }
}

帅气的冬瓜普通 2023年6月28日下午3:37

打卡

登录以回复

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(10)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复