消息关闭
    暂无新消息!

leetcode-为什么time limit exceeded?

问题作者 : 别克女2017-08-25发布

题目:颠倒一个singly linked list的顺序。比如:

1->2->3->4

需要一个function输出结果:

4->3->2->1

我写了一个简单recursion,但是一直显示time limit exceeded实在不知道为什么?

    ListNode* reverse(ListNode* &curr){
        if(curr->next==NULL){
            return curr;
        }
        return reverse(curr->next)->next = curr;
    }

注:ListNode的定义如下:

 struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

1个回答

︿ 0

把最终的结果打印出来,就知道为啥了.

void PrintList(list Node *p){
    while(p!=NULL){
        std::cout<<p->value<<std::endl;
        p=p->next;
    }
}

你的实现有两个问题:

  1. 1->2->3 经过翻转之后3->2->1, 也就是说reverse返回的头结点也应该变,你返回了curr 是不对的

  2. 翻转所有节点之后,原来的头结点next应该是NULL,你这个next没变动,所以1->2->1->2 循环了,leetcode测试用例就超时了.

可以试试:

  • 遍历,1->2->3 记住2下一个节点然后翻转,1<-2->3.. 依次遍历,这样你访问的最后一个节点就是 需要的头结点

  • 评论说的使用stack, 遍历压栈,最后栈顶就是需要的头指针.