i**9
发帖数: 351 | 1 void reversePairsOfLinkList(Node*& head) {
}
[] => []
[A,B] => [B, A]
[A, B, C] => [B, A, C]
[A, B, C, D, E, F, G] => [B, A, D, C, F, E, G]
这道题有些trick,我自己在白板上写的有些问题，在提示是下才写对。试试你能不能一
次写的无错误。(指定要对pointer操作，不能touch data) | H**d
发帖数: 152 | 2 void pairWiseSwap(struct node *head)
{
struct node *temp = head;
while(temp != NULL && temp->next != NULL)
{
swap(&temp->data, &temp->next->data);
temp = temp->next->next;
}
} | i**9
发帖数: 351 | 3 指定要对pointer操作，不能touch data
【在 H**d 的大作中提到】
: void pairWiseSwap(struct node *head)
: {
: struct node *temp = head;
: while(temp != NULL && temp->next != NULL)
: {
: swap(&temp->data, &temp->next->data);
: temp = temp->next->next;
: }
: }
| H**d
发帖数: 152 | 4 哦，pointer
快忘光了，
一会看你公布答案吧，呵呵
【在 i**9 的大作中提到】
: 指定要对pointer操作，不能touch data
| g********d
发帖数: 203 | 5 void reversePairsOfLinkList(Node **head) {
Node *c = *head;
if(!(*head)||!(*head->next)) return;
*head = *head->next;
while(c&&c->next){
n=c->next->next;
c->next->next=c;
c->next=n;
c=n;
}
} | g**e
发帖数: 6127 | 6 I think using recursion is easy to solve this
public static final Node reversePair(Node n) {
if (n==null || n.next==null)
return n;
Node first = n;
Node second = n.next;
Node third = second.next;
second.next = first;
first.next = reversePair(third);
return second;
}
【在 i**9 的大作中提到】
: void reversePairsOfLinkList(Node*& head) {
: }
: [] => []
: [A,B] => [B, A]
: [A, B, C] => [B, A, C]
: [A, B, C, D, E, F, G] => [B, A, D, C, F, E, G]
: 这道题有些trick,我自己在白板上写的有些问题，在提示是下才写对。试试你能不能一
: 次写的无错误。(指定要对pointer操作，不能touch data)
| n*******s
发帖数: 482 | 7 Node* partial_reverse(Node* head){
Node* headnew=head;
Node* p1 = head;
if(p1==NULL) return NULL;
Node* p2 = head->next;
Node* pre=NULL;
while(p2!=NULL){
if(headnew==head)
headnew = p2;
else
pre->next = p2;
p1->next = p2->next;
p2->next = p1;
pre = p1;
p1 = p1->next;
if(p1!=NULL)
p2 = p1->next;
else
break;
}
return headnew;
} | g*********s
发帖数: 1782 | 8 yes, recursion is easy for this one.
【在 g**e 的大作中提到】
: I think using recursion is easy to solve this
: public static final Node reversePair(Node n) {
: if (n==null || n.next==null)
: return n;
:
: Node first = n;
: Node second = n.next;
: Node third = second.next;
: second.next = first;
: first.next = reversePair(third);
|
| i**********e
发帖数: 1145 | 9 Gate:
很好！递归的确在某些情况可以更简单解决。
另外，guitarnerd 的代码有 bug，没有处理特殊状况。
这让我想起这道链表题，比这题还要更 tricky 些：
You are given two linked lists representing two non-negative numbers. The
digits are stored in reverse order and each of their nodes contain a single
digit. Add the two numbers and return it as a linked list.
你可以在这里输入你的代码，网站会自动以大量测试数据来检测你是否答对。你可以试
试看能不能第一次写就答对。
http://www.ihas1337code.com/onlinejudge
以下是我的递归与非递归的解法。
Iterative:
void reversePairsOfLinkList(Node *& head) {
if (!head) return;
Node *p1 = head;
while (p1) {
Node *p2 = p1->next;
if (!p2) return;
if (p1 == head)
head = p2;
Node *next = p2->next;
p2->next = p1;
p1->next = (next && next->next ? next->next : next);
p1 = next;
}
}
Recursive:
void recReverse(Node *& head) {
if (!head || !head->next) return;
Node *p1 = head->next;
Node *p2 = head->next->next;
p1->next = head;
head->next = p2;
head = p1;
recReverse(head->next->next);
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | f***g
发帖数: 214 | 10 我给贡献一个非递归的, 请指正
void rev() {
Node** cur = &head;
while( *cur!=0 && (*cur)->next!=0 ) {
Node* second = (*cur)->next;
(*cur)->next = second->next;
second->next = (*cur);
(*cur) = second;
cur = &((*cur)->next->next);
}
} | | | g**e
发帖数: 6127 | 11 你的网站做的挺不错的。
链表加法的题目不久前写了一个，主要是要注意进位（包括最后的最高位进一），还有
就是不同长度的两个链表的加法，当一个链表遍历结束，另外一个还没结束的时候，要
循环把没结束的那个全部加到结果去。用递归或循环做都行
single
【在 i**********e 的大作中提到】
: Gate:
: 很好！递归的确在某些情况可以更简单解决。
: 另外，guitarnerd 的代码有 bug，没有处理特殊状况。
: 这让我想起这道链表题，比这题还要更 tricky 些：
: You are given two linked lists representing two non-negative numbers. The
: digits are stored in reverse order and each of their nodes contain a single
: digit. Add the two numbers and return it as a linked list.
: 你可以在这里输入你的代码，网站会自动以大量测试数据来检测你是否答对。你可以试
: 试看能不能第一次写就答对。
: http://www.ihas1337code.com/onlinejudge
| i**********e
发帖数: 1145 | 12 恩，你说的对。
循环要考虑到各种状况，非常容易出错。而利用递归的思路就大大地把特别状况减少了。
我一直以为递归在没必要时都别用，因为容易出错。
但在这种情况之下，递归反而更不容易出错，相反循环解法相对复杂些而更容易导致错
误。
这让我对递归改观了，当循环的思路过于复杂的时候，尝试下递归的思路说不定能更简
洁些。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**e 的大作中提到】
: 你的网站做的挺不错的。
: 链表加法的题目不久前写了一个，主要是要注意进位（包括最后的最高位进一），还有
: 就是不同长度的两个链表的加法，当一个链表遍历结束，另外一个还没结束的时候，要
: 循环把没结束的那个全部加到结果去。用递归或循环做都行
:
: single
| g**e
发帖数: 6127 | 13 递归也就是面试的时候用用，production code用递归的还没见过，可能我看的少。我
觉得就算用也要加个递归层数的限制，不然程序容易崩溃
了。
【在 i**********e 的大作中提到】
: 恩，你说的对。
: 循环要考虑到各种状况，非常容易出错。而利用递归的思路就大大地把特别状况减少了。
: 我一直以为递归在没必要时都别用，因为容易出错。
: 但在这种情况之下，递归反而更不容易出错，相反循环解法相对复杂些而更容易导致错
: 误。
: 这让我对递归改观了，当循环的思路过于复杂的时候，尝试下递归的思路说不定能更简
: 洁些。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| s*****y
发帖数: 897 | 14 For the video decoder and audio decoder, commercial one.
Many decoder use the recursive call to extrace the header which is the video
and audio's metadata information. The function will recursive for 10-20, or
maybe 50. I forget why it needs to do in this way, but there is no better w
ay.
I encounter a lot of crash in this kind of function call due to the header n
oncompliant with standard. Most of these video are recorded by chinese "shan
zhai" cellphone.
【在 g**e 的大作中提到】
: 递归也就是面试的时候用用，production code用递归的还没见过，可能我看的少。我
: 觉得就算用也要加个递归层数的限制，不然程序容易崩溃
:
: 了。
| i**********e
发帖数: 1145 | 15 恩，没错。
Production code 就算有递归的形式也尽量会转成非递归的，因为栈容易溢出。
另外，速度上循环通常比递归的形式还要快。
通常的情况，递归总体来说 debug 起来还是比循环相比麻烦不少。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g**e 的大作中提到】
: 递归也就是面试的时候用用，production code用递归的还没见过，可能我看的少。我
: 觉得就算用也要加个递归层数的限制，不然程序容易崩溃
:
: 了。
| b******n
发帖数: 4509 | 16
if (head == NULL || head->next == NULL) return;
Node *temp = head->next, *temp2 = NULL;
if (temp->next == NULL || temp->next->next == NULL)
head->next = temp->next;
else {
head->next = temp->next->next;
temp2 = temp->next;
}
temp->next = head;
reversePairsOfLinkList(temp2 == NULL? temp->next : temp2);
【在 i**9 的大作中提到】
: void reversePairsOfLinkList(Node*& head) {
: }
: [] => []
: [A,B] => [B, A]
: [A, B, C] => [B, A, C]
: [A, B, C, D, E, F, G] => [B, A, D, C, F, E, G]
: 这道题有些trick,我自己在白板上写的有些问题，在提示是下才写对。试试你能不能一
: 次写的无错误。(指定要对pointer操作，不能touch data)
|
|
