leetcode-为什么time limit exceeded?

Question

题目：颠倒一个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) {}  };

Answer 1

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

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

你的实现有两个问题:

1->2->3 经过翻转之后3->2->1, 也就是说reverse返回的头结点也应该变，你返回了curr 是不对的
翻转所有节点之后，原来的头结点next应该是NULL，你这个next没变动，所以1->2->1->2 循环了，leetcode测试用例就超时了.

可以试试：

遍历，1->2->3 记住2下一个节点然后翻转，1<-2->3.. 依次遍历，这样你访问的最后一个节点就是需要的头结点
评论说的使用stack, 遍历压栈，最后栈顶就是需要的头指针.

leetcode-为什么time limit exceeded?

解决方案