由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 怎么理解递归解决的“swap every two elements in a linked list”?
相关主题
M家 onsite 悲剧,同胞们弄死烙印吧Add two linked list
一道挺简单的题给搞砸了到底怎么了?很多面试来的居然连reverse一个链表都写不来
Leetcode swap Paris 这个怎么改进?
相关话题的讨论汇总
话题: next话题: null话题: swap话题: second话题: first
进入JobHunting版参与讨论
1 (共1页)
n*****g
发帖数: 178
1
recursive的题我基本没怎么练过,基本只会BST中简单的查找之类的。我做得是网络方
面,感觉面试时候不太需要用到recursive。不过今天看到一面试题还是想弄明白其中
的recursive。想请教各位怎么理解?题目和解决方案如下:
Given a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->
null should become b->a->d->c->f->e->null). Code it such that memory
position is swapped and not the node value.
linknode* swap (linknode* root)
{
if (root==NULL || root->next==NULL)
return root;
linknode* first, *second;
first = root;
if(first && first->next)
{
second = root->next;
first->next= swap(second->next);//这里不太理解啊!!!!!!
second->next=first;
first=second;
}
return second;
}
p*****p
发帖数: 379
2
swap退栈的时候返回一组两个中的第二个,例如
1-2-3-4
1-2一组,3-4一组
a. swap(1)的时候执行到那行把2的next指向下个swap返回上来的node
b. 然后swap(3)被调用,返回node4,退栈
c. 4返回的时候又到a那步,2的next就拿到了4
然后继续走下去so on so forth
B********t
发帖数: 147
3
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(head == NULL || head->next == NULL)
return head;
else
{
ListNode *temp = head->next;
head->next = swapPairs(head->next->next);
temp->next = head;
return temp;
}
}

->

【在 n*****g 的大作中提到】
: recursive的题我基本没怎么练过,基本只会BST中简单的查找之类的。我做得是网络方
: 面,感觉面试时候不太需要用到recursive。不过今天看到一面试题还是想弄明白其中
: 的recursive。想请教各位怎么理解?题目和解决方案如下:
: Given a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->
: null should become b->a->d->c->f->e->null). Code it such that memory
: position is swapped and not the node value.
: linknode* swap (linknode* root)
: {
: if (root==NULL || root->next==NULL)
: return root;

c********t
发帖数: 5706
4
我不理解的是 那句 first=second;
需要吗?

->

【在 n*****g 的大作中提到】
: recursive的题我基本没怎么练过,基本只会BST中简单的查找之类的。我做得是网络方
: 面,感觉面试时候不太需要用到recursive。不过今天看到一面试题还是想弄明白其中
: 的recursive。想请教各位怎么理解?题目和解决方案如下:
: Given a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->
: null should become b->a->d->c->f->e->null). Code it such that memory
: position is swapped and not the node value.
: linknode* swap (linknode* root)
: {
: if (root==NULL || root->next==NULL)
: return root;

1 (共1页)
进入JobHunting版参与讨论
相关主题
Add two linked list一道挺简单的题给搞砸了
到底怎么了?很多面试来的居然连reverse一个链表都写不来Leetcode swap Paris 这个怎么改进?
M家 onsite 悲剧,同胞们弄死烙印吧
相关话题的讨论汇总
话题: next话题: null话题: swap话题: second话题: first