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

爱学习520

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

1. /**
   
2. * Definition for singly-linked list.
   
3. * struct ListNode {
   
4. *     int val;
   
5. *     struct ListNode *next;
   
6. * };
   
7. */
   
8. 
   
9. 
   
10. struct ListNode* reverseBetween(struct ListNode* head, int m, int n){
    
11. 
    
12.     int i;
    
13.     struct ListNode* p=head;
    
14.     struct ListNode* cur;
    
15.     struct ListNode* pre=NULL;
    
16.     struct ListNode* rev_head;
    
17.     struct ListNode*rev_tail;
    
18. 
    
19.     for(i=1;i<m;i++)
    
20.     {
    
21.         pre=p;
    
22.         p=p->next;
    
23.       
    
24.     }
    
25.      rev_head=pre;
    
26.      rev_tail=p->next;
    
27.    
    
28.     for (i=m;i<=n;i++)
    
29.     {
    
30.         cur=p->next;
    
31.         p->next=pre;
    
32.         pre=p;
    
33.         p=cur;
    
34.     }
    
35. 
    
36.     if(rev_head!=NULL)
    
37.     rev_head->next=pre;
    
38.     else
    
39.     head=pre;
    
40.    
    
41. 
    
42.     rev_tail=p;
    
43.    
    
44.     return head;
    
45.    
    
46. 
    
47.    
    
48. 
    
49. }

复制代码

最佳答案

月排行榜 / 总排行榜

赚小钱

2020-7-9 22:42:25

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

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

先说第一点

你这两行的代码和

1. int a = 0;
   
2. a = 1;
   
3. a = 2;

复制代码

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

而且

1. a = b->next
   
2. a = c

复制代码

与

1. a = b
   
2. a->next = c

复制代码

区别还是很大的吧。

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

1. a = b
   
2. b = c

复制代码

得出

1. a = c

复制代码

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

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

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

一模一样

以上

跳转到最佳答案楼层

小甲鱼的铁粉

建议发一下完整题目

爱学习520

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

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

说明:
1 ≤&#160;m&#160;≤&#160;n&#160;≤ 链表长度。

示例:

输入: 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

赚小钱

1. struct ListNode *reverseBefore(struct ListNode *head, int n) {
   
2.     if (head == NULL || head->next == NULL) {
   
3.         return head;
   
4.     }
   
5.     struct ListNode* prev = head;
   
6.     struct ListNode *current = head->next;
   
7.     for (int i = 0; i < n && current != NULL; i++) {
   
8.         struct ListNode * next = current ->next;
   
9.         current->next = prev;
   
10.         prev = current;
    
11.         current = next;
    
12.     }
    
13.     head->next = current;
    
14.     return prev;
    
15. }
    
16. 
    
17. struct ListNode *reverseBetween(struct ListNode *head, int m, int n) {
    
18.     struct ListNode *beforeM = head;
    
19.     for (int i = 1; i < m - 1; i++) {
    
20.         beforeM = beforeM->next;
    
21.     }
    
22.     if (m == 1) {
    
23.         return reverseBefore(beforeM, n-m);
    
24.     }
    
25.     beforeM->next = reverseBefore(beforeM->next, n - m);
    
26.     return head;
    
27. }
    

复制代码

赚小钱

L26 修改为

1.      rev_tail=p;

复制代码

L42 修改为

1.     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. 你没有理清，开始反转的节点的前一个节点是本题的关键

先说第一点

你这两行的代码和

1. int a = 0;
   
2. a = 1;
   
3. a = 2;

复制代码

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

而且

1. a = b->next
   
2. a = c

复制代码

与

1. a = b
   
2. a->next = c

复制代码

区别还是很大的吧。

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

1. a = b
   
2. b = c

复制代码

得出

1. a = c

复制代码

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

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

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

一模一样

以上

爱学习520

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

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