leetcode 92. 反转链表 II

一时失言乱红尘 2023-06-30 15:57 35阅读 0赞

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:  
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4  
输出: 1->4->3->2->5->NULL

思路： dfs+回溯时修改链表

我觉得没啥可以分析的。只要理解了dfs的过程，然后稍微处理一下边界条件即可。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            if(head==NULL) return NULL;
            ListNode *ans = new ListNode(0);
            ListNode *p=head;
            ListNode *q=NULL;
            ListNode *last=new ListNode(0);
            int k=1;
            while(k<m)
            {
                q=p;
                p=p->next;
                k++;
            }
            //cout<<k<<endl;
            dfs(p,NULL,ans,last,m,n,k);
            //cout<<last->val<<endl;
            if(q==NULL) return ans;
            else q->next=ans;
            return head;
            
        }
         void dfs(ListNode *head,ListNode *pre,ListNode *&ans,ListNode *&last, int m,int n,int k)
        {
            if(k<=n)
            {
                int tmp=k;
                tmp++;
                dfs(head->next,head,ans,last,m,n,tmp);
            }
            if(k==n) ans=head;
            if(k==n+1)
            {
                last=head;
                return;
            }
            if(k==m)
            {
                head->next=last;
                return;
            }
            head->next=pre;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-92. 反转链表 II

题目来源 [206. 反转链表][206.] 1、我们定义两个指针，分别称之为 g(guard 守卫) 和 p(point)。我们首先根据方法的参数 m 确定 g 和

男娘i/ 2024年03月22日 15:44/ 0 赞/ 55 阅读

相关 leetcode 92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->5->NULL, m =

一时失言乱红尘/ 2023年06月30日 15:57/ 0 赞/ 36 阅读

相关【LeetCode 92】反转链表 II

题目描述反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->

叁歲伎倆/ 2023年02月17日 02:29/ 0 赞/ 27 阅读

相关【链表】 LeetCode92. 反转链表 II

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

水深无声/ 2022年12月02日 13:37/ 0 赞/ 169 阅读

相关 leetcode算法【92】反转链表 II

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

ゝ一世哀愁。/ 2022年11月25日 04:25/ 0 赞/ 128 阅读

相关 LeetCode92. 反转链表 II

难度：`中等` 题目描述： > 给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置

爱被打了一巴掌/ 2022年11月10日 14:27/ 0 赞/ 177 阅读

相关 LeetCode 92. 反转链表 II

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

一时失言乱红尘/ 2022年11月10日 14:27/ 0 赞/ 150 阅读

相关 Leetcode 92. 反转链表 II

题目重述给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节

待我称王封你为后i/ 2022年10月19日 05:41/ 0 赞/ 176 阅读

相关 92. 反转链表 II

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

╰半夏微凉°/ 2022年10月17日 11:27/ 0 赞/ 169 阅读

相关【LeetCode】92. 反转链表 II

题目链接：[https://leetcode-cn.com/problems/reverse-linked-list-ii/description/][https_leetco

素颜马尾好姑娘i/ 2022年05月11日 11:20/ 0 赞/ 182 阅读