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. 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, 遍历压栈，最后栈顶就是需要的头指针.