请问：两个笔试题
1 如何在不引入第三个变量的条件下交换变量a和b的值，三步完成？
2 一个单链表，不知道长度，如何快速找到中间节点的位置？
问题点数：20、回复次数：61Top
1 楼steel007（小宝)(工作在windows和linux平台上）回复于 2005-11-13 11:01:39 得分 0
1.xor
2.我想，用两个指针吧，一个递增1，一个递增2，如果第二个到头了，第一个就是在中间结点上面了。Top
2 楼csucdl（csucdl）回复于 2005-11-13 11:05:34 得分 0
steel007(小宝)(工作在windows和linux平台上)
想法不错Top
3 楼csucdl（csucdl）回复于 2005-11-13 11:14:21 得分 20
1：
a ^= b ^= a ^= b
2
Link *temp1 = head;
Link *temp2 = head;
if(temp1 == NULL)
return NULL;
while(temp2->next != NULL && temp2->next->next != NULL)
{
temp1 = temp1->next;
temp2 = temp2->next->next;
}
return temp1;Top
4 楼csucdl（csucdl）回复于 2005-11-13 11:17:14 得分 0
while(temp2 != NULL && temp2->next != NULL)
{
temp1 = temp1->next;
temp2 = temp2->next->next;
}
return temp1;Top
5 楼yetyongjin（云梦谭）回复于 2005-11-13 11:29:29 得分 0
我來答第一題吧：
a += b; //把兩個數的和賦給a
b = a-b; //然後和-b就是a的值給變量b
a -=b; //和-b(值已經是原來變量a的值）得出交換結果Top
6 楼arthas19（网络的边缘·_·）回复于 2005-11-13 13:14:23 得分 0
a ^= b ^= a ^= b 是什么意思啊？Top
7 楼jianlirong（简）回复于 2005-11-13 13:39:39 得分 0
如果你想实现问题（2）的功能，我建议你学习一下跳表，那是一种链表，但不是单链表，但可以很快实现你所需的功能。Top
8 楼Mr_Yang（初级程序员）回复于 2005-11-13 13:49:46 得分 0
1,a = a+b;
b = a-b;
a = a-b;Top
9 楼wjvlangz（清菜虫虫）回复于 2005-11-13 14:01:48 得分 0
好方法，学习了Top
10 楼youruhe（又如何）回复于 2005-11-13 14:07:15 得分 0
第一题在谭书上有的
a ^= b;
b ^= a;
a ^= b;
//
a = a+b;
b = a-b;
a = a-b;
在某些情况下也是适用的，但是它有一个让你难以查找的BUG：a+b可能溢出
Top
11 楼tiansf85（小田）回复于 2005-11-13 15:27:16 得分 0
方法真的很好，值得学习。谢谢！Top
12 楼conquer2004（狗样年华）回复于 2005-11-13 22:02:32 得分 0
yetyongjin(云梦谭)
强！Top
13 楼biduan（笔端）回复于 2005-11-13 22:04:29 得分 0
2.我想，用两个指针吧，一个递增1，一个递增2，如果第二个到头了，第一个就是在中间结点上面了。
//不错哦！Top
14 楼mooncome_a（云破月来）回复于 2005-11-13 22:18:22 得分 0
这不是11.12清华同方在南开招聘的C++考题之二吗?Top
15 楼A39033261（）回复于 2005-11-13 22:56:17 得分 0
a=a+b;
b=a-b;
a=a-bTop
16 楼goodsun1（）回复于 2005-11-14 02:59:58 得分 0
dingTop
17 楼pongba（刘未鹏|http://blog.csdn.net/pongba）回复于 2005-11-14 05:17:06 得分 0
大家对第二题的答复固然精妙，但你们有没有算一下时间复杂度？准确一点说时间复杂度是(3/2)n，因为第二个指针完整遍历了整个链表，第一个指针遍历了一半。1+1/2 ^_^
而最简单最直接的算法： 先遍历一遍链表求出长度（实际上，一个不傻的链表实现在获取长度时时间复杂度为常数），然后长度/2，接着按照这个一半长度遍历至中点即可。时间复杂度顶多也是(3/2)n。而且我刚才说了，获取单链表长度，对于一个不傻的单链表实现来说是常数时间的，所以时间复杂度可为(1/2)n。
所以结论是，算法虽然精妙，但用平实的算法也一样丝毫不吃亏，甚至还有容易编码，不易出错，阅读容易，在可常数时间获取链表长度的时候还更有优势^_^
当然，跳表是首选。复杂度为O(1)。Top
18 楼csucdl（csucdl）回复于 2005-11-14 08:35:04 得分 0
楼上的是不是专攻算法的
厉害，真所谓术业有专攻Top
19 楼csucdl（csucdl）回复于 2005-11-14 08:36:19 得分 0
不傻的链表应该就是长度已知的罗Top
20 楼pongba（刘未鹏|http://blog.csdn.net/pongba）回复于 2005-11-14 08:58:33 得分 0
呵呵，不是长度已知，是可以跟踪长度，真正实际中使用的链表类哪个不能在常数时间内获取size()？;-)Top
21 楼tailzhou（尾巴）回复于 2005-11-14 10:24:42 得分 0
一个单链表，不知道长度，如何快速找到中间节点的位置？
都说了不知道长度了，还罗嗦一大堆Top
22 楼lilinll77（小孬）回复于 2005-11-14 10:42:42 得分 0
第二题还有没有其他更好的解法？Top
23 楼peipeiguo（Percy）回复于 2005-11-14 11:33:16 得分 0
学习一下Top
24 楼chary8088（天使鱼儿）回复于 2005-11-14 13:49:36 得分 0
tailzhou(尾巴) ( )
不知道长度是原始条件,并不是不可以求出长度!!!Top
25 楼chary8088（天使鱼儿）回复于 2005-11-14 13:50:19 得分 0
第2题
Link *temp = head;
int flag=0,length=0;
if(temp->next==NULL)
return;
while(temp->next!=NULL)
{
length++;
}
while(temp->next!=NULL&&flag!=(length/2))
{
flag++;
temp=temp->next;
}
return temp;
Top
26 楼cxyol（C++,VC 学习中......）回复于 2005-11-14 17:38:08 得分 0
a=a+b;
b=a-b;
a=a-b
这个最好Top
27 楼Featured（我握着爱情的门票静静排队……）回复于 2005-11-14 18:24:46 得分 0
呵呵，不是长度已知，是可以跟踪长度，真正实际中使用的链表类哪个不能在常数时间内获取size()？;-)
========
“跟踪长度”是不是遍历一遍？
那还不是一样的复杂度Top
28 楼pongba（刘未鹏|http://blog.csdn.net/pongba）回复于 2005-11-14 18:37:02 得分 0
跟踪长度需要遍历一遍吗？每次插入的时候把计数器增一就可以了嘛，我说的是一个链表类。
当然，就算遍历一遍求长度，复杂度仍然是3/2n。Top
29 楼ihavenoidea（正）回复于 2005-11-14 19:34:00 得分 0
T* p = first;
vector<T*> helpArr;
whle(p)
{
helpArr.push_back(p);
p = p->next;
}
return helpArr[helpArr.size()/2];
// 类似这样如何,虽然增加了空间HOHOTop
30 楼ihavenoidea（正）回复于 2005-11-14 19:36:37 得分 0
while(temp2 != NULL && temp2->next != NULL)
{
temp1 = temp1->next;
temp2 = temp2->next->next;
}
return temp1;
// 顺便说下,我觉得这个的应该算 O(1/2 n) 吧~~ 用这个也可以检测链表循环啊~ 呵!Top
31 楼alienation（雅蛋）回复于 2005-11-14 20:51:13 得分 0
指向下下个的那个
链表的长度为1的时候出错了吧Top
32 楼pongba（刘未鹏|http://blog.csdn.net/pongba）回复于 2005-11-14 20:52:49 得分 0
ihavenoidea:
用vector不是找抽嘛-_-~姑且不说它暗地里会重分配内存，一个正统的vector实现，当你的链表长为n的时候，导致vector重分配log(n)次内存，每次都会搬动2^i个元素，sigma(2^i)[i从1至log(n)] = n。即n次拷贝开销（如果vector用memcpy则稍微好一点），再加上log(n)次重分配内存的开销，后者的开销占主体地位！
更何况你在时间复杂度上也根本没讨到好处，时间复杂度仍然是n，如果算上push_back的赋值开销则是2n，总体上没有逃脱O(n)。
至于原来那个算法，复杂度总体为O(n)（线性）。精确的说，如果把temp2!=nulL,temp2->next, temp2->next!=null,temp1->next,temp1=temp1->next; ..都算一次操作的话，时间复杂度为n/2+n/2+n/2+n/2+n/2+ 3(n/2) = 8(n/2) = 4n;
-_-~Top
33 楼Grubby_c（This time tell me the truth）回复于 2005-11-14 21:01:10 得分 0
什么是跳表？
google搜不到Top
34 楼ihavenoidea（正）回复于 2005-11-14 21:13:06 得分 0
谢谢指教 :)
不过我写的可能具体点了 . 我说的是用这样的想法~~
替换 vector 的方法多的是啊. 当然加上赋值 又是2N +++ 了 呵呵
再顺便说下 上面俺说错了 HOHO 不是1/2N 是 3/2N 是俺原来理解不好 :):)
当然不管杂样都是线性的
算了 再细就没意思了
Top
35 楼pongba（刘未鹏|http://blog.csdn.net/pongba）回复于 2005-11-14 21:30:30 得分 0
grubby: 搜skiplistTop
36 楼Eminens（阿木）回复于 2005-11-14 22:49:00 得分 0
学习Top
37 楼fly_qj（青蛙王子）回复于 2005-11-17 20:59:03 得分 0
markTop
38 楼fly_qj（青蛙王子）回复于 2005-11-19 13:41:15 得分 0
不过 a+b 可能溢出这个Bug一定得时时放在心里啊.Top
39 楼kgdiawpyu（祥子）回复于 2005-11-19 14:02:09 得分 0
学习！Top
40 楼yingpf（阿飛）回复于 2005-11-19 16:41:27 得分 0
个人认为，pongba说的没错啊，从时间复杂度来考虑的话，的确是这样的，而且csucdlr的算法中，各位难道觉的下面这两个比较不用花时间吗:
temp2->next != NULL && temp2->next->next != NULL
记得在数据结构中，数组结构有一种应用“岗哨”的技巧，就是为了消除这种循环中的比较而出现的。Top
41 楼yazoox（考拉）回复于 2005-11-20 23:25:18 得分 0
好贴. 拍个爪印先.
mark.
下面的兄弟继续.
Top
42 楼qizhirui（其其）回复于 2005-11-21 00:19:34 得分 0
学习Top
43 楼aishuishui021（）回复于 2005-11-21 09:50:44 得分 0
一个相当不错的数据结构，类似AVL，支持插入，查找，删除，任何时候都可以
看成一个有序的链表。实现相当简单，性能也相当不错，当然这是一个概率算法，
一切的性能都是在概率意义上的，但同样因为这是一个概率算法，就像是快速
排序一样，没有特定的一个最坏情况的输入，因此作为常用数据结构当然是很爽的了。
只是有一个问题，这个数据结构基础上实现一些其他的数据结构不是那么明了，
比如顺序统计树，这个要是完美的解决的话，这个数据结构绝对是常用工具箱中的极品了。Top
44 楼CrackerF（测试中，请勿打扰）回复于 2005-11-21 10:33:35 得分 0
第一题用异或没问题。
第二题我喜欢steel007小宝的想法，赞一个！
Top
45 楼bm1408（向va_list学习~不用VC好多年~）回复于 2005-11-21 10:36:54 得分 0
a =a ^b;
b = b^a
a= a^b;Top
46 楼2004csharp（）回复于 2005-11-21 15:45:28 得分 0
我顶
Top
47 楼langzi520（虽左但右）回复于 2005-11-21 19:12:15 得分 0
第一题
a=a+b;
b=a-b;
a=a-b；
第二题
Link *temp = head;
int flag=0,length=0;
if(temp->next==NULL)
return;
while(temp->next!=NULL)
{
length++;
}
while(temp->next!=NULL&&flag!=(length/2))
{
flag++;
temp=temp->next;
}
return temp;
Top
48 楼tiansf85（小田）回复于 2005-11-21 22:01:12 得分 0
请问这个贴有多久了?我都看过好多遍了.难道这么多答案都没有符合楼主的吗?Top
49 楼widowss（widowss）回复于 2005-11-21 22:15:58 得分 0
pongba(刘未鹏|《Imperfect C++》|《Exceptional C++ Style》) :
2楼的方法怎么会是3/2n的复杂度呢，应该是1/2n吧，因为每次跳转2步到头的时候，我也跳转一步，前者跳转到链表末尾是1/2nTop
50 楼ihavenoidea（正）回复于 2005-11-22 12:17:04 得分 0
int c = 10;
int &a=c;
int &b=c;
例外~Top
51 楼wdwggyy（懒懒蝴蝶）回复于 2005-11-22 20:28:11 得分 0
第一题,学习;
第二题,看了几遍,
一头雾水,
不知道哪个最好.Top
52 楼zloves（俺是菜鸟）回复于 2005-11-23 11:08:11 得分 0
第一个问题两种算法如前面人所说的，提醒一下，用异或时要注意两个数必须是整型或者是字符型，用a+=b;b=a-b;a-=b;要注意a+b可能溢出
对于个问题，向请教一下 steel007(小宝)(工作在windows和linux平台上)
对于你的想法：用两个指针吧，一个递增1，一个递增2，如果第二个到头了，第一个就是在中间结点上面；
请问怎样判断第二个指针到头了呢？
是不是判断它为NUll时？
我的对这个的理解是（举个例子）
1 2 3 4 5 6
两个指针p1,p2一开始都指向1,p2+=2,p1++,
当p2到头（也就是为NULL)时，p1指向4（如你所说）
但是当
1 2 3 4 5 6 7 时
p2为NULL时
p1指向5呀，
小弟菜鸟一个，请指教Top
53 楼gsqwolf（七匹狼之白狼）回复于 2005-11-23 11:36:19 得分 0
学习中。。。。。。。。。。。。Top
54 楼ilovedudu（void *）回复于 2005-11-23 11:44:21 得分 0
今天突然有了灵感了，嘿嘿...
第一题楼上都解答了，偶来答第2题....
LINK* SearchMiddleNode(LINK *pHead)
{
LINK *pMiddle;
int count;
Top
55 楼ilovedudu（void *）回复于 2005-11-23 11:45:15 得分 0
不好意思，按错键了
Top
56 楼ilovedudu（void *）回复于 2005-11-23 12:03:54 得分 0
LINK* SearchMiddleNode(LINK *pHead)
{
LINK *pMiddle=pHead;
int count=0;
if(pHead->next == NULL)
{
printf("空表");
return NULL;
}
for(LINK *pTem=pHead->next; pTem != NULL; pTem=pTem->next)
{
count++;
if(count%2 != 0) // 关键的地方....
{
pMeddle=pMeddle->next;
}
}
return pMeddle;
}
Top
57 楼luojxun（）回复于 2005-11-23 12:06:00 得分 0
一个递增一个递减,想法不错,单链表是无法实现的,因为链表不是连续的存储的.双链表道是可以的.Top
58 楼ilovedudu（void *）回复于 2005-11-23 12:13:02 得分 0
输入有误，pMeddle 应为pMeddle
Top
59 楼ilovedudu（void *）回复于 2005-11-23 12:13:54 得分 0
输入还是有误，改为pMiddleTop
60 楼haosimentu（）回复于 2005-11-23 14:19:51 得分 0
应该差不多的:
void main(void)
{
char str[128];
printf("please input:");
scanf("%s",str);
char *p1,*p2;
p1=p2=str;
while(*p2!='\0')
{
p1+=1;
p2+=2;
}
printf("%c",*p1);
}Top
61 楼bader（）回复于 2005-11-24 00:35:40 得分 0
对于问题1，有本书叫《高效程序的奥秘》（中译本，ISBN：7111141113），原著为《Hacker's Delight》（ISBN：0201914654），专门就此类接近底层的细节问题进行了讨论。这类问题的思考角度通常在位和字节，而像问题2这样的DS问题则更多地涉及队列、栈、树这种高一层次的结构；两类问题严格地说是不太一样的。Top
