返回信息流给定一单链表A1->A2->A3->......->AN, 转换为A2->A1->A4->A3->.....->AN(如果N是偶数），转换为A1->A3->A2->A5->A4->....->AN(如果N是奇数），要求是只能便利一遍链表。
这是一条镜像帖。来源：北邮人论坛 / cpp / #33612同步于 2009/12/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
问一个面试题，链表相关的
youziboy
2009/12/17镜像同步14 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
奇偶是事先知道么？如果是偶，这样可以么？
p=x1
while(p>next>next!=null)
{temp=p>next>next
p>next>next=p
p>next=temp>next
p=temp}
最后处理最后一对
P>next>next=p
p>next=null
procedure process(p, n)
begin
if p has next
if (r = process(p->next, n+1)) mod 4 == 0
do swaps ......(像2楼写的那样)
return r+1
endif
else return 1
endif
end
框架就是这样了
可以把链表看成.....A4->A3->A2->A1.
忽略奇数偶数的区别。
T* reverseLinkedList(T* p, int& n) {
if(p == null) {
n = 1;
return;
}
if(n%2 == 0) {
reverseLinkedList(p->next, n);
T* pTmp = p->next;
p->next = p->next-next;
pTmp->next = p;
++n;
return pTmp;
else {
p->next = reverseLinkedList(p->next, n);
++n;
return p;
}
}
【 在 youziboy 的大作中提到: 】
: 给定一单链表A1->A2->A3->......->AN, 转换为A2->A1->A4->A3->.....->AN(如果N是偶数），转换为A1->A3->A2->A5->A4->....->AN(如果N是奇数），要求是只能便利一遍链表。
好像明白你的意思，从最后这么做，但是是不是应该mod2，而且先把最后两个做好？是不是只要P有下一个，就要返回r+1。所以你那个r+1的位置是不是有点问题？你这样做应该就是不考虑长度了，所以那个n是不是没用啊？
【 在 jokerlee 的大作中提到: 】
: procedure process(p, n)
: begin
: if p has next
: ...................