f*******r
发帖数: 1086 | 1 大家都知道有一个简单的singly linked list面试
题目就是reverse singly linked list.
在与MS欧洲电面的过程中，interviewer要我online
coding出这个函数，我因为之前都复习过，很快
写了一个recursive 版本的代码:
SLNode* head;
SLNode* Reverse(SLNode* root)
{
assert(root!=NULL);
if(root->next!=NULL)
{
Reverse(root->next);
root->next->next = root;
return(root);
}
else
head = root;
}
当时想法是代码简洁一点，但是interviewer看过后
问我如果用recursion的话，会有什么问题？经提示
才想到，recursion会使用stack memory，当链表
的节点非常多的时候会有问题，这个的确是开始写
这个函数的时候没有考虑到scales上的问题， |
Z*****Z
发帖数: 723 | 2 谢分享，bless
【在 f*******r 的大作中提到】
: 大家都知道有一个简单的singly linked list面试
: 题目就是reverse singly linked list.
: 在与MS欧洲电面的过程中，interviewer要我online
: coding出这个函数，我因为之前都复习过，很快
: 写了一个recursive 版本的代码:
: SLNode* head;
: SLNode* Reverse(SLNode* root)
: {
: assert(root!=NULL);
: if(root->next!=NULL)
|
r****o
发帖数: 1950 | 3 Linked List的最初的head指针是不是应该保存下来，最后指向NULL?
【在 f*******r 的大作中提到】
: 大家都知道有一个简单的singly linked list面试
: 题目就是reverse singly linked list.
: 在与MS欧洲电面的过程中，interviewer要我online
: coding出这个函数，我因为之前都复习过，很快
: 写了一个recursive 版本的代码:
: SLNode* head;
: SLNode* Reverse(SLNode* root)
: {
: assert(root!=NULL);
: if(root->next!=NULL)
|
f*******r
发帖数: 1086 | 4 Sorry,是的，这个的确是需要的！
在else里面给head赋值之前加一句
head.next = NULL;
head = root;
应该就可以了。
【在 r****o 的大作中提到】
: Linked List的最初的head指针是不是应该保存下来，最后指向NULL?
|
p******r
发帖数: 2999 | 5 node* reverse(nood* root) {
node *head, *tail, *temp;
if(root==null) return null;
head=tail=root;
while(tail->next != null) {
temp=tail->next;
tail->next=temp->next; // remove one element after tail
temp->next=head; // insert it to the head
head=temp;
}
return head;
}
【在 f*******r 的大作中提到】
: 大家都知道有一个简单的singly linked list面试
: 题目就是reverse singly linked list.
: 在与MS欧洲电面的过程中，interviewer要我online
: coding出这个函数，我因为之前都复习过，很快
: 写了一个recursive 版本的代码:
: SLNode* head;
: SLNode* Reverse(SLNode* root)
: {
: assert(root!=NULL);
: if(root->next!=NULL)
|
d**f
发帖数: 264 | 6 Node* Reverse(Node* head){
Node *current, *next, *result;
current = head;
result =NULL;
while( current != NULL ){
next = current->next;
current->next = result;
result = current;
current = next;
};
return result;
}; |
