[已解决]leetcode这个超时怎么解决，帮忙看看

爱学习520

在leetcode上面做的一个链表反转的题目，把链表第m和n的部分反转，我觉得我代码应该没有问题，为什么会超时，希望大佬指出一下错误，代码很简单，希望大家帮忙看一下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseBetween(struct ListNode* head, int m, int n){

    int i;
    struct ListNode* p=head;
    struct ListNode* cur;
    struct ListNode* pre=NULL;
    struct ListNode* rev_head;
    struct ListNode*rev_tail;

    for(i=1;i<m;i++)
    {
        pre=p;
        p=p->next;
       
    }
     rev_head=pre;
     rev_tail=p->next;
    
    for (i=m;i<=n;i++)
    {
        cur=p->next;
        p->next=pre;
        pre=p;
        p=cur; 
    }

    if(rev_head!=NULL)
    rev_head->next=pre;
    else
    head=pre;
    

    rev_tail=p;
    
    return head;
    

    

}

最佳答案

月排行榜 / 总排行榜

赚小钱

2020-7-9 22:42:25

爱学习520 发表于 2020-7-9 21:47
你这两个修改后不是和我的效果一模一样吗  一个往前了，一个往后了

你有两个问题：
1. 变量 rev_tail 是一个没有被使用的变量，你的代码把 L26 L42 这两行删掉，完全不影响你的逻辑
2. 你没有理清，开始反转的节点的前一个节点是本题的关键

先说第一点

你这两行的代码和

int a = 0;
a = 1;
a = 2;

的含义有什么本质的差别呢, 只有声明定义赋值的变量叫做无用变量

而且

a = b->next
a = c

与

a = b
a->next = c

区别还是很大的吧。

编程不等价于数学
在数学里，你可以有等量代换

a = b
b = c

得出

a = c

而编程，是需要考虑内存的
你的 rev_tail 只是一个指针变量，你修改他的值，只是让他指向了另一个地方，而谁又关心他指哪呢，使用它的目的，是为了记录链表中的某个关键的位置（本体中是开始反转的节点的前一个）
最后将 rev_tail->next 指向反转之后的头结点。

而你的 rev_tail 指向的是 被反转的起始位置，
链表之所以被称为链表，在于相邻的两个节点直接，通过 next field 产生了关系，而你却抛弃了 next

最后，拿到别人的代码先思考一下，再不行，还可以上 leetcode 提交一下，别一上来就说

一模一样

以上

跳转到最佳答案楼层

小甲鱼的铁粉

建议发一下完整题目

爱学习520

小甲鱼的铁粉 发表于 2020-7-9 19:33
建议发一下完整题目

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

赚小钱

struct ListNode *reverseBefore(struct ListNode *head, int n) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* prev = head;
    struct ListNode *current = head->next;
    for (int i = 0; i < n && current != NULL; i++) {
        struct ListNode * next = current ->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head->next = current;
    return prev;
}

struct ListNode *reverseBetween(struct ListNode *head, int m, int n) {
    struct ListNode *beforeM = head;
    for (int i = 1; i < m - 1; i++) {
        beforeM = beforeM->next;
    }
    if (m == 1) {
        return reverseBefore(beforeM, n-m);
    }
    beforeM->next = reverseBefore(beforeM->next, n - m);
    return head;
}

赚小钱

L26 修改为

     rev_tail=p;

L42 修改为

    rev_tail->next=p;

只说一下你的变量命名，L30 的变量，明显应该用 next 啊，你用的 cur，让我看起来特别影响思路。

爱学习520

赚小钱 发表于 2020-7-9 21:01
L26 修改为

你这两个修改后不是和我的效果一模一样吗  一个往前了，一个往后了

赚小钱

爱学习520 发表于 2020-7-9 21:47
你这两个修改后不是和我的效果一模一样吗  一个往前了，一个往后了

你有两个问题：
1. 变量 rev_tail 是一个没有被使用的变量，你的代码把 L26 L42 这两行删掉，完全不影响你的逻辑
2. 你没有理清，开始反转的节点的前一个节点是本题的关键

先说第一点

你这两行的代码和

int a = 0;
a = 1;
a = 2;

的含义有什么本质的差别呢, 只有声明定义赋值的变量叫做无用变量

而且

a = b->next
a = c

与

a = b
a->next = c

区别还是很大的吧。

编程不等价于数学
在数学里，你可以有等量代换

a = b
b = c

得出

a = c

而编程，是需要考虑内存的
你的 rev_tail 只是一个指针变量，你修改他的值，只是让他指向了另一个地方，而谁又关心他指哪呢，使用它的目的，是为了记录链表中的某个关键的位置（本体中是开始反转的节点的前一个）
最后将 rev_tail->next 指向反转之后的头结点。

而你的 rev_tail 指向的是 被反转的起始位置，
链表之所以被称为链表，在于相邻的两个节点直接，通过 next field 产生了关系，而你却抛弃了 next

最后，拿到别人的代码先思考一下，再不行，还可以上 leetcode 提交一下，别一上来就说

一模一样

以上

爱学习520

赚小钱 发表于 2020-7-9 22:42
你有两个问题：
1. 变量 rev_tail 是一个没有被使用的变量，你的代码把 L26 L42 这两行删掉，完全不影响 ...

非常感谢你的耐心解答 因为昨天太晚没有电脑运行，所以没有仔细看，抱歉。今天看了一下，你对我的问题回复的很精准，让我找到到问题 非常感谢啦。嘻嘻