爱学习520 发表于 2020-7-9 17:06:19

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

在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 19:33:21

建议发一下完整题目

爱学习520 发表于 2020-7-9 19:38:13

小甲鱼的铁粉 发表于 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

赚小钱 发表于 2020-7-9 20:38:22

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

赚小钱 发表于 2020-7-9 21:01:59

L26 修改为
   rev_tail=p;

L42 修改为
    rev_tail->next=p;


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

爱学习520 发表于 2020-7-9 21:47:11

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




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

赚小钱 发表于 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-10 10:28:28

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

非常感谢你的耐心解答 因为昨天太晚没有电脑运行，所以没有仔细看，抱歉。今天看了一下，你对我的问题回复的很精准，让我找到到问题 非常感谢啦{:5_109:}。嘻嘻
页: [1]
查看完整版本: leetcode这个超时怎么解决，帮忙看看