再问一下：有人用ATT用optimus L9的吗？ - 未名空间MITBBS历史存档

再问一下：有人用ATT用optimus L9的吗？# PDA - 掌中宝

h*w2013-01-21 08:01

1 楼

总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
很不nice, 问了个reverse each pair of node in singly-linked list
就是1->2->3->4->5
得到2->1->4->3->5
我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
recursion写出来了。
谁知道给个只用reference, 或pointer来解个

s*g2013-01-21 08:01

2 楼

天热，闲的蛋疼，画了图
如需visio 原图，请pm. 价格10个包子。

m*t2013-01-21 08:01

3 楼

能用3g吗？还是EDGE only？
谢谢

C*U2013-01-21 08:01

4 楼

重新构造两个list？
用两个指针就可以
一个是指向所有奇数位的node的head
一个是指向偶数的位的node的指针
然后合并回来
只多用两个指针
时间是3n

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

J*h2013-01-21 08:01

5 楼

难道这是传说中的沙发？

t*m2013-01-21 08:01

6 楼

用的时候图标显示的是4G。用speedtest测下载8kbps(对,不是Mbps),上载1.1Mbps.
浏览网页速度明显比EDGE快5倍8倍的。觉得算是3G速度吧。

【在 m******t 的大作中提到】

: 能用3g吗？还是EDGE only？
: 谢谢

h*w2013-01-21 08:01

7 楼

对呀，好解法。我就笨了
555，剩下四个人都搞定了，就差这么一个，死烙印

【在 C***U 的大作中提到】

: 重新构造两个list？
: 用两个指针就可以
: 一个是指向所有奇数位的node的head
: 一个是指向偶数的位的node的指针
: 然后合并回来
: 只多用两个指针
: 时间是3n

x*i2013-01-21 08:01

8 楼

晕！

m*t2013-01-21 08:01

9 楼

有意思，8k连拨号/edge都不如.上传倒是有tmobile 4g的平均速度了。

【在 t*****m 的大作中提到】

: 用的时候图标显示的是4G。用speedtest测下载8kbps(对,不是Mbps),上载1.1Mbps.
: 浏览网页速度明显比EDGE快5倍8倍的。觉得算是3G速度吧。

C*U2013-01-21 08:01

10 楼

面试得时候紧张选了不是最好的方法也正常的

【在 h********w 的大作中提到】

: 对呀，好解法。我就笨了
: 555，剩下四个人都搞定了，就差这么一个，死烙印

w*r2013-01-21 08:01

11 楼

虽然很不屑里面的内容
但还要赞一个，思维清晰，简单易懂。
是个闲才。

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

l*l2013-01-21 08:01

12 楼

是3G的。
这个手机大部分地方给出的频段specs都是错的，所以你会以为只包括了这边tmobile
3G频段。其实是全频段的。

【在 m******t 的大作中提到】

: 能用3g吗？还是EDGE only？
: 谢谢

d*w2013-01-21 08:01

13 楼

我来写一个java的
public ListNode swapPairs(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if (head == null || head.next == null)
return head;

ListNode newNode = head.next;
ListNode p;
ListNode cur = head;
while(head != null && head.next != null) {
p = head.next.next;

head.next.next = head;
if (p != null)
head.next = p.next;
else
head.next = null;
cur = head;
head = p;
}

if (head != null)
cur.next = head;
return newNode;
}

【在 h********w 的大作中提到】

: 对呀，好解法。我就笨了
: 555，剩下四个人都搞定了，就差这么一个，死烙印

s*g2013-01-21 08:01

14 楼

好说好说。。

【在 w*******r 的大作中提到】

: 虽然很不屑里面的内容
: 但还要赞一个，思维清晰，简单易懂。
: 是个闲才。

s*n2013-01-21 08:01

15 楼

if (head==NULL || head->next==NULL) return head;
Node* newhead = head->next;
Node* last = NULL;
Node* cursor = head;
while (cursor && cursor->next) {
Node* newposition = cursor->next->next;
if (last!=NULL) last->next = cursor->next;
cursor->next->next = cursor;
last = cursor;
cursor = newposition;
}
if (last!=NULL) last->next = cursor;
return newhead;

M*t2013-01-21 08:01

16 楼

打酱油的不止我们三个吧？
画得不错，其实那天我也想画个来着，不过我想的是四格漫画。后来忙就没画。

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

g*y2013-01-21 08:01

17 楼

不一定被搞死见了5个人希望》90%

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

s*g2013-01-21 08:01

18 楼

期待漫画

【在 M*****t 的大作中提到】

: 打酱油的不止我们三个吧？
: 画得不错，其实那天我也想画个来着，不过我想的是四格漫画。后来忙就没画。

q*x2013-01-21 08:01

19 楼

五个不少了。没见大老板？如果黄，不会是老印一个人的问题，说明第四第五个也不是
很满意。

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

M*t2013-01-21 08:01

20 楼

赞“闲才”。哈哈。。。
你和石头发展得怎么样了？找个时间出去喝个咖啡嘛。

【在 w*******r 的大作中提到】

: 虽然很不屑里面的内容
: 但还要赞一个，思维清晰，简单易懂。
: 是个闲才。

h*w2013-01-21 08:01

21 楼

这样了，第5个没考我programming, 问了些别的问题
如MS的产品改进，可怜我近2年一直用apple,可能没太答好

【在 q****x 的大作中提到】

: 五个不少了。没见大老板？如果黄，不会是老印一个人的问题，说明第四第五个也不是
: 很满意。

M*t2013-01-21 08:01

22 楼

最近太忙，估计没时间画。

【在 s***g 的大作中提到】

:
: 期待漫画

b*u2013-01-21 08:01

23 楼

貌似这题你的确没答好。。

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

m*u2013-01-21 08:01

24 楼

不错不错

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

A*u2013-01-21 08:01

25 楼

实习？
有机会帮你报仇
我也讨厌老印

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

w*r2013-01-21 08:01

26 楼

你再跟我提那个烂人，
我会对你动粗的！！

【在 M*****t 的大作中提到】

: 赞“闲才”。哈哈。。。
: 你和石头发展得怎么样了？找个时间出去喝个咖啡嘛。

S*02013-01-21 08:01

27 楼

直接交换数字

s*g2013-01-21 08:01

28 楼

好奇，怎么个动粗法？

【在 w*******r 的大作中提到】

: 你再跟我提那个烂人，
: 我会对你动粗的！！

q*x2013-01-21 08:01

29 楼

what is his title? sounds like a big boss.
even you are apple user, you can still provide suggestions.

【在 h********w 的大作中提到】

: 这样了，第5个没考我programming, 问了些别的问题
: 如MS的产品改进，可怜我近2年一直用apple,可能没太答好

w*r2013-01-21 08:01

30 楼

可以骂人，可以找斑竹，
也可以找黑社会，
要看本小姐的心情了。

【在 s***g 的大作中提到】

:
: 好奇，怎么个动粗法？

h*w2013-01-21 08:01

31 楼

I didn't ask his title, and he should be a boss.
I provide some suggestions, but not sound interesting to him.

【在 q****x 的大作中提到】

: what is his title? sounds like a big boss.
: even you are apple user, you can still provide suggestions.

M*t2013-01-21 08:01

32 楼

错了，我一打酱油的，不想卷进去。

【在 w*******r 的大作中提到】

: 你再跟我提那个烂人，
: 我会对你动粗的！！

h*w2013-01-21 08:01

33 楼

Full time SDET, 555,没机会去M家了

【在 A**u 的大作中提到】

: 实习？
: 有机会帮你报仇
: 我也讨厌老印

s*g2013-01-21 08:01

34 楼

黑涩会。。怕怕
这么一说，更觉得你跟某人（省略。。以免被人施暴）的关系诡异了。如果真那么恨
，早就“奈伊做特了”。实际情况是，天天上来隔空xx, 境界太高。。。。
我一工科男，无法理解。我就此打住。

【在 w*******r 的大作中提到】

: 可以骂人，可以找斑竹，
: 也可以找黑社会，
: 要看本小姐的心情了。

s*f2013-01-21 08:01

35 楼

此题电脑和人脑的解法一样的。纸上划一划

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

w*r2013-01-21 08:01

36 楼

切。。。

【在 s***g 的大作中提到】

:
: 黑涩会。。怕怕
: 这么一说，更觉得你跟某人（省略。。以免被人施暴）的关系诡异了。如果真那么恨
: ，早就“奈伊做特了”。实际情况是，天天上来隔空xx, 境界太高。。。。
: 我一工科男，无法理解。我就此打住。

x*y2013-01-21 08:01

37 楼

这个有问题吧？！

【在 d********w 的大作中提到】

: 我来写一个java的
: public ListNode swapPairs(ListNode head) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (head == null || head.next == null)
: return head;
:
: ListNode newNode = head.next;
: ListNode p;
: ListNode cur = head;

M*t2013-01-21 08:01

38 楼

人，可以找斑竹，

【在 s***g 的大作中提到】

:
: 黑涩会。。怕怕
: 这么一说，更觉得你跟某人（省略。。以免被人施暴）的关系诡异了。如果真那么恨
: ，早就“奈伊做特了”。实际情况是，天天上来隔空xx, 境界太高。。。。
: 我一工科男，无法理解。我就此打住。

G*o2013-01-21 08:01

39 楼

M家没啥意思，尤其是SDET。直接上A/G/F。

【在 h********w 的大作中提到】

: Full time SDET, 555,没机会去M家了

M*t2013-01-21 08:01

40 楼

习惯就好了。那不算啥。比这热的哥也过来了。

【在 s***g 的大作中提到】

:
: 黑涩会。。怕怕
: 这么一说，更觉得你跟某人（省略。。以免被人施暴）的关系诡异了。如果真那么恨
: ，早就“奈伊做特了”。实际情况是，天天上来隔空xx, 境界太高。。。。
: 我一工科男，无法理解。我就此打住。

s*n2013-01-21 08:01

41 楼

用个bool flag就知道当前位置，奇数就reverse,过一遍就行了

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

l*t2013-01-21 08:01

42 楼

期待四格漫画，希望挤一点时间搞一下

【在 M*****t 的大作中提到】

: 打酱油的不止我们三个吧？
: 画得不错，其实那天我也想画个来着，不过我想的是四格漫画。后来忙就没画。

w*x2013-01-21 08:01

43 楼

其实... 题没做出来不能怪种族, 楼主第一想到的因该是提高自己的能力是吧.

B*02013-01-21 08:01

44 楼

虽然有图,可还是不懂.感觉比基金公司的风险精算还难.

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

i*e2013-01-21 08:01

45 楼

应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
考点是注意链表为空，链表只有一个值的corner cases。
还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴和下一个 pair 头部。
要特别注意。
另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
给个例子：
链表： 1->2->3->4->5
k = 2, 返回: 2->1->4->3->5
k = 3, 返回: 3->2->1->4->5
这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴
和下一个 group 头部。

【在 C***U 的大作中提到】

: 重新构造两个list？
: 用两个指针就可以
: 一个是指向所有奇数位的node的head
: 一个是指向偶数的位的node的指针
: 然后合并回来
: 只多用两个指针
: 时间是3n

M*t2013-01-21 08:01

46 楼

BSO你会精算。

【在 B******0 的大作中提到】

: 虽然有图,可还是不懂.感觉比基金公司的风险精算还难.

S*02013-01-21 08:01

47 楼

部。
能不能贴一个k group的solution, 我觉得那个很难code出来

【在 i**********e 的大作中提到】

: 应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
: 考点是注意链表为空，链表只有一个值的corner cases。
: 还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴和下一个 pair 头部。
: 要特别注意。
: 另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
: 给个例子：
: 链表： 1->2->3->4->5
: k = 2, 返回: 2->1->4->3->5
: k = 3, 返回: 3->2->1->4->5
: 这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴

y*o2013-01-21 08:01

48 楼

才子！

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

L*52013-01-21 08:01

49 楼

一下程序只用了两个指针 prev 和 post （已经验证过啦是对的哦）
我分别讨论了三种情况 (1) < 2 node (2) = 2 node (3) > 2 node
对于大于两个node的情况（初始化 prev = 第一个node，post = 第二个node），
以奇数 node 为 current， prev 设为 current 前一个， post设为current->next。
void PairReverse (Node **headpt) {
//None node or one-node case
if (*headpt == NULL || (*headpt) -> next == NULL) {
printf ("Less than two nodes are in the list.\n");
return;
}
Node *prev = *headpt, *post = (*headpt) -> next;
//Two-node case
//e.g. 1 2, then 1 - prev, 2- post
prev -> next = post -> next;
post -> next = prev;
*headpt = post;
post = prev -> next;
if (!post)
return;
//More than two-node case
//e.g. 1 2 | 3 4 | 5, then 2 - prev, 4 - post
while (post && post -> next) {
post = post -> next;
prev -> next -> next = post -> next;
post -> next = prev -> next;
prev -> next = post;
prev = post -> next;
post = prev -> next;
}
}

B*02013-01-21 08:01

50 楼

“会”子谈不上，尚在学习认知阶段。不过理论上讲，只要有充足准确的数据，并明确
目标，很多非经济
金融领域的问题，甚至两性关系、家庭婚姻都可以进行运算，推断出一定的概率。

【在 M*****t 的大作中提到】

: BSO你会精算。

s*52013-01-21 08:01

51 楼

有一次面试被要求一个小时答三个问题，这个是其中之一，不同的是每N个node就要
reverse，N可变。稍微超时，不过做出来了，给出compilable drug-free code，拿到onsite机会。下面是C++ code:
不需要讨论很多情况的。
Node* reverseN(int N, Node* list)
{
Node *next = NULL, *prev = NULL;
int final = N;
Node *tail1 = list;
while( list && list->data <= final )
{
next = list->next;
list->next = prev;
prev = list;
list = next;
}
Node *head = prev; // Head of the resulting linked list.
while( list )
{
final += N;
prev = NULL;
Node* tail2 = list;
while( list && list->data <= final )
{
next = list->next;
list->next = prev;
prev = list;
list = next;
}
tail1->next = prev;
tail1 = tail2;
}
return head;
}

l*g2013-01-21 08:01

52 楼

一看你就没有认真看贴。
wendy孟是40+的massage女。容貌出现两个，需要被确认。我觉的还是倾向照片里的，
有亲密照，有真相。
frank35岁小白脸。
老处女36岁研究生。容貌未知。

【在 s***g 的大作中提到】

: 天热，闲的蛋疼，画了图
: 如需visio 原图，请pm. 价格10个包子。

h*w2013-01-21 08:01

53 楼

总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
很不nice, 问了个reverse each pair of node in singly-linked list
就是1->2->3->4->5
得到2->1->4->3->5
我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
recursion写出来了。
谁知道给个只用reference, 或pointer来解个

B*02013-01-21 08:01

54 楼

抱歉!小生初来乍到,对这一片儿的江湖深浅和新闻旧闻的内幕了解不多.也就随口一说,
您大人大量,千
万别当真.往后还得请列为大侠多多提携帮衬.

【在 l******g 的大作中提到】

: 一看你就没有认真看贴。
: wendy孟是40+的massage女。容貌出现两个，需要被确认。我觉的还是倾向照片里的，
: 有亲密照，有真相。
: frank35岁小白脸。
: 老处女36岁研究生。容貌未知。

C*U2013-01-21 08:01

55 楼

重新构造两个list？
用两个指针就可以
一个是指向所有奇数位的node的head
一个是指向偶数的位的node的指针
然后合并回来
只多用两个指针
时间是3n

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

l*g2013-01-21 08:01

56 楼

是你画的？

说,

【在 B******0 的大作中提到】

: 抱歉!小生初来乍到,对这一片儿的江湖深浅和新闻旧闻的内幕了解不多.也就随口一说,
: 您大人大量,千
: 万别当真.往后还得请列为大侠多多提携帮衬.

h*w2013-01-21 08:01

57 楼

对呀，好解法。我就笨了
555，剩下四个人都搞定了，就差这么一个，死烙印

【在 C***U 的大作中提到】

: 重新构造两个list？
: 用两个指针就可以
: 一个是指向所有奇数位的node的head
: 一个是指向偶数的位的node的指针
: 然后合并回来
: 只多用两个指针
: 时间是3n

l*g2013-01-21 08:01

58 楼

你是STBUG的马甲？

说,

【在 B******0 的大作中提到】

: 抱歉!小生初来乍到,对这一片儿的江湖深浅和新闻旧闻的内幕了解不多.也就随口一说,
: 您大人大量,千
: 万别当真.往后还得请列为大侠多多提携帮衬.

C*U2013-01-21 08:01

59 楼

面试得时候紧张选了不是最好的方法也正常的

【在 h********w 的大作中提到】

: 对呀，好解法。我就笨了
: 555，剩下四个人都搞定了，就差这么一个，死烙印

B*02013-01-21 08:01

60 楼

图跟我一点关系也没有，我只是好奇所以看看热闹。在下BRIC8590（Steven）绝非他人
马甲。您可以
进一步验证。

【在 l******g 的大作中提到】

: 你是STBUG的马甲？
:
: 说,

d*w2013-01-21 08:01

61 楼

我来写一个java的
public ListNode swapPairs(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if (head == null || head.next == null)
return head;

ListNode newNode = head.next;
ListNode p;
ListNode cur = head;
while(head != null && head.next != null) {
p = head.next.next;

head.next.next = head;
if (p != null)
head.next = p.next;
else
head.next = null;
cur = head;
head = p;
}

if (head != null)
cur.next = head;
return newNode;
}

【在 h********w 的大作中提到】

: 对呀，好解法。我就笨了
: 555，剩下四个人都搞定了，就差这么一个，死烙印

b*w2013-01-21 08:01

62 楼

我是路见不平的大妈。态度同石头大叔。
FRANK 同36岁老女人的关系是 EX BF & GF，或者包养关系。
FRANK 同 WENDY 关系是 EX-EX BF & GF 兼雇佣关系，非包养关系。
资金从 WENDY 和 FRANK 之间是工资或生意合作伙伴分红。
这个养字我要说下。一个老板可以说，我手下养了1000个人，这1000人是给他干活的啊
。 FRANK 可以说是 WENDY 的这样提供工作机会（进化妆品和搭理店铺）的养法，不是
包养的养。可以说30岁老女人是被 FRANK 包养的。
结论：36女被包养3-4个月，由于性格等种种原因，FRANK 忍受不了，离她而去。数个
月杳无音讯，偏执36岁女开始在网上报复寻人。FRANK 不出面，36 岁女目的未达到，
ID 还被封。

s*n2013-01-21 08:01

63 楼

if (head==NULL || head->next==NULL) return head;
Node* newhead = head->next;
Node* last = NULL;
Node* cursor = head;
while (cursor && cursor->next) {
Node* newposition = cursor->next->next;
if (last!=NULL) last->next = cursor->next;
cursor->next->next = cursor;
last = cursor;
cursor = newposition;
}
if (last!=NULL) last->next = cursor;
return newhead;

l*g2013-01-21 08:01

64 楼

FRANK跟WENDY是同居多年后才认识36岁的老处女。他在隐瞒他们的同居关系的情况下追
求老处女。
WENDY自己说她给了FRANK很多钱，FRANK给她提供性服务的，而且她还出钱让他追别的
女生，这是变态的包养。如果FRANK对后来追的36岁的老处女是真心追求，那就是男女
朋友关系，如果不是，他们很有可能从事的是色情行业，故意陷害良家女子，这是逼良
为娼的行为。

，

【在 b********w 的大作中提到】

: 我是路见不平的大妈。态度同石头大叔。
: FRANK 同36岁老女人的关系是 EX BF & GF，或者包养关系。
: FRANK 同 WENDY 关系是 EX-EX BF & GF 兼雇佣关系，非包养关系。
: 资金从 WENDY 和 FRANK 之间是工资或生意合作伙伴分红。
: 这个养字我要说下。一个老板可以说，我手下养了1000个人，这1000人是给他干活的啊
: 。 FRANK 可以说是 WENDY 的这样提供工作机会（进化妆品和搭理店铺）的养法，不是
: 包养的养。可以说30岁老女人是被 FRANK 包养的。
: 结论：36女被包养3-4个月，由于性格等种种原因，FRANK 忍受不了，离她而去。数个
: 月杳无音讯，偏执36岁女开始在网上报复寻人。FRANK 不出面，36 岁女目的未达到，
: ID 还被封。

g*y2013-01-21 08:01

65 楼

不一定被搞死见了5个人希望》90%

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

b*w2013-01-21 08:01

66 楼

说话要看有依据来源。虽然现在来源基本上是看WENDY 和老处女分别怎么说。
WENDY 同大妈说是 FRANK 为她打工进货的。石头大叔也是说WENDY这么说的。如果你要
说这是提供性服务拿钱，那么很多人也在男女朋友手下工作过，这也算提供性服务了，
那么就打到一大片。
关于是否脚踏两只船，WENDY同大妈说，他们是在老处女前的前男女朋友。该老处女也
说了，wendy 说是他们两个人是再她之前，并不干涉他们交往。WENDY FRANK 分手后就
是朋友和雇佣关系。用常理想想看，要是FRANK 是不干活被WENDY包养的，WENDY 绝对
不会对FRANK这么客气，而且默认FRANK 和老处女的关系。FRANK 经济上我敢断定是自
立的，他才能这样摆平WENDY。
关于逼良为娼的事情我也不太赞成。要真是逼良为娼，我估计是这样的 1. 不会等几个
月，2.这么多钱和心思不太会去找36岁的，而会去找更年轻的 3. 按照生意经，生意
人衡量付出得到，几个月付出 “何止上万”+ 时间OPPORTUNITY COST, 这怕是亏本买
卖啊。4.FRANK 最后离开，不是老处女离开。
总之，我不太喜欢老处女的行为。捞钱了得好处得照顾了还倒打人一耙。看热闹的人她
也要打。我说到她的痛处根本，即她没有工作经济来源，身份有非法嫌疑，她对我很恼
火。估计最近FRANK离开了她,她的生存压力也很大。导致她在网上撒野。碰到复杂的事
情，我喜欢从最根本的经济和生存方面方面去想。
大妈我真是闲得发慌了。我就此收手了。

【在 l******g 的大作中提到】

: FRANK跟WENDY是同居多年后才认识36岁的老处女。他在隐瞒他们的同居关系的情况下追
: 求老处女。
: WENDY自己说她给了FRANK很多钱，FRANK给她提供性服务的，而且她还出钱让他追别的
: 女生，这是变态的包养。如果FRANK对后来追的36岁的老处女是真心追求，那就是男女
: 朋友关系，如果不是，他们很有可能从事的是色情行业，故意陷害良家女子，这是逼良
: 为娼的行为。
:
: ，

q*x2013-01-21 08:01

67 楼

五个不少了。没见大老板？如果黄，不会是老印一个人的问题，说明第四第五个也不是
很满意。

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

l*g2013-01-21 08:01

68 楼

其实不论年龄大小，身份国籍，指使自己的男人出来勾引欺骗单纯女生的都够变态的，
那样的女的都跟妓女差不多。也不知道这样的女人跟自己的男人除了性关系还有什么在
里面。

，

【在 b********w 的大作中提到】

: 我是路见不平的大妈。态度同石头大叔。
: FRANK 同36岁老女人的关系是 EX BF & GF，或者包养关系。
: FRANK 同 WENDY 关系是 EX-EX BF & GF 兼雇佣关系，非包养关系。
: 资金从 WENDY 和 FRANK 之间是工资或生意合作伙伴分红。
: 这个养字我要说下。一个老板可以说，我手下养了1000个人，这1000人是给他干活的啊
: 。 FRANK 可以说是 WENDY 的这样提供工作机会（进化妆品和搭理店铺）的养法，不是
: 包养的养。可以说30岁老女人是被 FRANK 包养的。
: 结论：36女被包养3-4个月，由于性格等种种原因，FRANK 忍受不了，离她而去。数个
: 月杳无音讯，偏执36岁女开始在网上报复寻人。FRANK 不出面，36 岁女目的未达到，
: ID 还被封。

h*w2013-01-21 08:01

69 楼

这样了，第5个没考我programming, 问了些别的问题
如MS的产品改进，可怜我近2年一直用apple,可能没太答好

【在 q****x 的大作中提到】

: 五个不少了。没见大老板？如果黄，不会是老印一个人的问题，说明第四第五个也不是
: 很满意。

b*w2013-01-21 08:01

70 楼

大妈我闲得发慌，被骂得也不爽，骂我是孟小姐，骂我是什么什么女。
查询一番发现骂我的shenyanger (peter liu) 是
niuwa, laoxiang 的老马甲。骂人口吻一致，IP 地址一致，上站时间吻合。
查询shenyanger (peter liu) ，发现这个ID 写了一文名 “我是王芳的老公”，然后
顺藤摸瓜，发现shenyanger同德克萨斯著名的 google90 (王芳)IP一致，骂人口吻一致。
案情复杂，情节起伏，出人意料，STBug是不是要再画一张图？
骂人帖子被删除，但犹豫被引用起来，证据还在

发信人: shenyanger (peter liu), 信区: Texas
标题: 我是王芳的老公
发信站: BBS 未名空间站 (Sat Jul 3 18:58:42 2010, 美东)
其实我就是王芳的老公。是我对不起所有的人。都是我败坏了男人的名声，丢了所有男
人的脸。因为我以前遇到的女孩看不起我破坏别人家庭，找老女人睡觉，所以老女人让
我回国找个小的回来，本来还想把她女儿介绍给我呢，就是那个UTD的。现在我们结婚
都N年了，又是一个地方的人，其实我觉的跟我老婆挺般配的，虽然她比我小10多岁。
但是我还离不开那个老女人，没办法呀，谁让我没出息的。
你们谴责我吧。现在她要跟我离婚了，你们说我是不是还得回国再搬运一个。
发信人: google90 (王芳), 信区: Texas
标题: Re: 【挖个坑】回忆最打击你的一句话。。
发信站: BBS 未名空间站 (Mon Sep 20 19:03:58 2010, 美东)
老公是个偷渡来美国的，他说回国随便在大学旁边租个房子就有一堆学生等着跟他同居
被带到美国来，他已经39岁了。他想找什么样的女人都能找到。我就是被他从国内带来
的被他说成是便宜自行车的。
我们是沈阳的。
发信人: google90 (王芳), 信区: Texas
标题: Re: 王芳，我喜欢听你的故事
发信站: BBS 未名空间站 (Wed Jun 30 22:59:44 2010, 美东)
我是来美国上语言学校的。
女主娘家德州人对她的故事总结：
发信人: qianli (钱礼), 信区: Texas
标题: 王芳，我喜欢听你的故事
发信站: BBS 未名空间站 (Sun Jun 13 18:10:22 2010, 美东)
不过故事挺复杂的。你看我理解的对不对？
一切要从你那天杀的老公谈起。
0，有一个杭州女的，结了婚的，自己带女儿出来了，老公扔国内不管了，现在有房子，
是公民，当破鞋，搞破鞋的还不是你老公，他那时还没来。
1，有个男傻逼，旅游签证，过来后政治避难了，然后当了男破鞋，和那个杭州女人。
2，傻逼男拿到公民后，不愿意当破鞋男了，想尝尝鲜，回沈阳把你弄来了。于是傻逼男
变成了你老公。
3，杭州女没操够你老公，你老公一根烂枪两头戳，弹药不够，被你发现了。
4，杭州女为了留住你老公这杆烂枪，把自己女儿的处女膜献给了你老公，当然也可能不
是处女了，告诉你老公买一送一。古有狡兔三窟，你老公现在也有三窟，算上你的。
5，你现在有两个敌人，但第一敌人不是那个杭州女，一个老烂逼用不了多久你老公就会
日够了，现在第一敌人是那个比你还水灵的杭州女的女儿。该女，UT达拉斯EE专业的。
6，你现在就要把这个嫩女搞臭，尽管你老公也是臭肉，但是，失身于他也没啥办法了，
连英文都看不懂，咋办呢，吃肉吧。
7，你老公要回国，你来问问GCD会不会找你老公的麻烦，我告诉你，不会！只要你老公
办的政治庇护不是法轮功，共产党不会找他麻烦，地下教会还是一胎都没问题。法轮功
有问题，前两天一个轮子坐了20多个小时飞机到上海，人家海关查出来他是法轮功，立
马让他又花20多个小时飞回美国了。
8，你现在究竟是怎么想的？你最恶心的是杭州老破鞋，还是杭州小妖精？还是烂枪三窟
的你老公？每天晚上看着你老公当过破鞋的那杆烂枪，你就一点点洁癖都没有吗？他在
你身体里进出的时候，你不恶心吗？表示同情。
以上8点都是根据你的文章写的，哪理解不对，还望指正。
咱就事论事，不搞人身攻击。
接下来估计是女主搬离德州来到加州，是否离婚了未知。在隐瞒婚史的情况下，自称处
女，或误导他人认为是处女，先后在网上认识王某和FRANK. 王某和FRANK分别由于种种
原因离开女主角，且音讯杳无。女主发怒，加上只有美国语言学校学历，找工作难上加
难。于是因爱生恨，迁怒于两位男主角的女性朋友们（或者女友们），开始在买买提各
大版网上寻人，演绎一场场悲壮的情感故事。
咱也搞事论事，不搞人身攻击。以上总结基于女主的发帖。
不知网上相亲还有多少类似故事发生，还是指腹为婚的好。

b*u2013-01-21 08:01

71 楼

貌似这题你的确没答好。。

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

m*t2013-01-21 08:01

72 楼

旧瓶装新酒。赞。

致。
在这
子，
逼男
能不
就会
了，
三窟

【在 b********w 的大作中提到】

: 大妈我闲得发慌，被骂得也不爽，骂我是孟小姐，骂我是什么什么女。
: 查询一番发现骂我的shenyanger (peter liu) 是
: niuwa, laoxiang 的老马甲。骂人口吻一致，IP 地址一致，上站时间吻合。
: 查询shenyanger (peter liu) ，发现这个ID 写了一文名 “我是王芳的老公”，然后
: 顺藤摸瓜，发现shenyanger同德克萨斯著名的 google90 (王芳)IP一致，骂人口吻一致。
: 案情复杂，情节起伏，出人意料，STBug是不是要再画一张图？
: 骂人帖子被删除，但犹豫被引用起来，证据还在
:
: 发信人: shenyanger (peter liu), 信区: Texas
: 标题: 我是王芳的老公

A*u2013-01-21 08:01

73 楼

实习？
有机会帮你报仇
我也讨厌老印

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

S*02013-01-21 08:01

74 楼

直接交换数字

q*x2013-01-21 08:01

75 楼

what is his title? sounds like a big boss.
even you are apple user, you can still provide suggestions.

【在 h********w 的大作中提到】

: 这样了，第5个没考我programming, 问了些别的问题
: 如MS的产品改进，可怜我近2年一直用apple,可能没太答好

h*w2013-01-21 08:01

76 楼

I didn't ask his title, and he should be a boss.
I provide some suggestions, but not sound interesting to him.

【在 q****x 的大作中提到】

: what is his title? sounds like a big boss.
: even you are apple user, you can still provide suggestions.

h*w2013-01-21 08:01

77 楼

Full time SDET, 555,没机会去M家了

【在 A**u 的大作中提到】

: 实习？
: 有机会帮你报仇
: 我也讨厌老印

s*f2013-01-21 08:01

78 楼

此题电脑和人脑的解法一样的。纸上划一划

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

x*y2013-01-21 08:01

79 楼

这个有问题吧？！

【在 d********w 的大作中提到】

: 我来写一个java的
: public ListNode swapPairs(ListNode head) {
: // Start typing your Java solution below
: // DO NOT write main() function
: if (head == null || head.next == null)
: return head;
:
: ListNode newNode = head.next;
: ListNode p;
: ListNode cur = head;

G*o2013-01-21 08:01

80 楼

M家没啥意思，尤其是SDET。直接上A/G/F。

【在 h********w 的大作中提到】

: Full time SDET, 555,没机会去M家了

s*n2013-01-21 08:01

81 楼

用个bool flag就知道当前位置，奇数就reverse,过一遍就行了

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

w*x2013-01-21 08:01

82 楼

其实... 题没做出来不能怪种族, 楼主第一想到的因该是提高自己的能力是吧.

i*e2013-01-21 08:01

83 楼

应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
考点是注意链表为空，链表只有一个值的corner cases。
还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴和下一个 pair 头部。
要特别注意。
另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
给个例子：
链表： 1->2->3->4->5
k = 2, 返回: 2->1->4->3->5
k = 3, 返回: 3->2->1->4->5
这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴
和下一个 group 头部。

【在 C***U 的大作中提到】

: 重新构造两个list？
: 用两个指针就可以
: 一个是指向所有奇数位的node的head
: 一个是指向偶数的位的node的指针
: 然后合并回来
: 只多用两个指针
: 时间是3n

S*02013-01-21 08:01

84 楼

部。
能不能贴一个k group的solution, 我觉得那个很难code出来

【在 i**********e 的大作中提到】

: 应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
: 考点是注意链表为空，链表只有一个值的corner cases。
: 还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴和下一个 pair 头部。
: 要特别注意。
: 另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
: 给个例子：
: 链表： 1->2->3->4->5
: k = 2, 返回: 2->1->4->3->5
: k = 3, 返回: 3->2->1->4->5
: 这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴

L*52013-01-21 08:01

85 楼

一下程序只用了两个指针 prev 和 post （已经验证过啦是对的哦）
我分别讨论了三种情况 (1) < 2 node (2) = 2 node (3) > 2 node
对于大于两个node的情况（初始化 prev = 第一个node，post = 第二个node），
以奇数 node 为 current， prev 设为 current 前一个， post设为current->next。
void PairReverse (Node **headpt) {
//None node or one-node case
if (*headpt == NULL || (*headpt) -> next == NULL) {
printf ("Less than two nodes are in the list.\n");
return;
}
Node *prev = *headpt, *post = (*headpt) -> next;
//Two-node case
//e.g. 1 2, then 1 - prev, 2- post
prev -> next = post -> next;
post -> next = prev;
*headpt = post;
post = prev -> next;
if (!post)
return;
//More than two-node case
//e.g. 1 2 | 3 4 | 5, then 2 - prev, 4 - post
while (post && post -> next) {
post = post -> next;
prev -> next -> next = post -> next;
post -> next = prev -> next;
prev -> next = post;
prev = post -> next;
post = prev -> next;
}
}

s*52013-01-21 08:01

86 楼

有一次面试被要求一个小时答三个问题，这个是其中之一，不同的是每N个node就要
reverse，N可变。稍微超时，不过做出来了，给出compilable drug-free code，拿到onsite机会。下面是C++ code:
不需要讨论很多情况的。
Node* reverseN(int N, Node* list)
{
Node *next = NULL, *prev = NULL;
int final = N;
Node *tail1 = list;
while( list && list->data <= final )
{
next = list->next;
list->next = prev;
prev = list;
list = next;
}
Node *head = prev; // Head of the resulting linked list.
while( list )
{
final += N;
prev = NULL;
Node* tail2 = list;
while( list && list->data <= final )
{
next = list->next;
list->next = prev;
prev = list;
list = next;
}
tail1->next = prev;
tail1 = tail2;
}
return head;
}

l*a2013-01-21 08:01

87 楼

写了个递归版本的。
ListNode *swapPairs(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
ListNode * h1 = head;
ListNode* h4 = NULL;
if(h1->next && h1->next->next){
h4 = swapPairs(head->next->next);
}
ListNode * h2 = h1->next;
h1->next = h4;
h2->next = h1;
return h2;
}

h*n2013-01-21 08:01

88 楼

我的递归和非递归解法，贴在下面 OJ通过，还有每K个reverse那个，不过那个只有递
归版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
/*
//递归做法很简单，但是要切记前面几行的顺序，别放错了
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* next = cur->next;
if(next==NULL) return cur;

ListNode* nextnext = next->next;
next->next = cur;
cur->next = swapPairs(nextnext);
return next;
*/
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* next = cur->next;
if(next == NULL) return cur;
ListNode* res = next;
ListNode* nextnext;
while(cur&&next)
{
nextnext = next->next;
next->next = cur;
if(nextnext)
{
if(nextnext->next)
{
cur->next = nextnext->next;
}
else
{
cur->next = nextnext;
}
//别忘了更新cur和next
cur=nextnext;
next = cur->next;
}
else
{
//这个else别忘了很重要，否则变成循环链表了
cur->next = NULL;
break;
}
}
return res;
}
};
Reverse in K-group
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!head) return NULL;
ListNode* cur = head;
int i = 0;
while(cur)
{
i++;
if(i>=k) break;
cur = cur->next;
}
if(ireturn head;

ListNode* pre = NULL;
ListNode* next;
cur = head;
i = k;
while(cur && i>0)
{
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
i--;
}

head->next = reverseKGroup(cur, k);
//这里要注意reverse的是pre
return pre;
}
};

h*n2013-01-21 08:01

89 楼

说实话，这个题也算基本题。不能怪他为难你，楼主还是加油吧啊

r*m2013-01-21 08:01

90 楼

我面2sigma电面的时候碰到了这个题，还好在OJ上写过了。
当时只给了电面的最后10分钟要求写出来。

h*n2013-01-21 08:01

91 楼

递归的话还是时间够的，一共就7-8行

【在 r*******m 的大作中提到】

: 我面2sigma电面的时候碰到了这个题，还好在OJ上写过了。
: 当时只给了电面的最后10分钟要求写出来。

r*m2013-01-21 08:01

92 楼

对，code是就那么短，也不一定要递归，定义指针的指针就很方便

【在 h****n 的大作中提到】

: 递归的话还是时间够的，一共就7-8行

w*x2013-01-21 08:01

93 楼

彩虹mm~~~~~~~

【在 r*******m 的大作中提到】

:
: 对，code是就那么短，也不一定要递归，定义指针的指针就很方便

n*e2013-01-21 08:01

94 楼

写个:P:
public void reversepair(Node head){
if(head == null) return;
Node second ==head.next;
Node first == head;
while(first != null && second !=null){
first.next = second.next;
second.next = first;
first = first.next;
second = first.next.next;
}
}
望大家指出问题~

n*e2013-01-21 08:01

95 楼

有个小问题这样写了以后head指的就不是头了，要把head改成head.next.

【在 n******e 的大作中提到】

: 写个:P:
: public void reversepair(Node head){
: if(head == null) return;
: Node second ==head.next;
: Node first == head;
: while(first != null && second !=null){
: first.next = second.next;
: second.next = first;
: first = first.next;
: second = first.next.next;

j*e2013-01-21 08:01

96 楼

我的解法，是一个普遍的k解法。在main里面把k改为2或者是面试官喜欢的k的值就ok。
希望大家指正。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NOT write main() function

int num = 1;
if (head == null) return null;
ListNode count = head;
while (count.next != null) {
num++;
count = count.next;
}
if (num/k <1)
return head;
int times = num/k;

ListNode front = head;
int nodes = 0;
while (times > 0) {
times--;
nodes = k;
rotate(front, k);
while (nodes > 0) {
front = front.next;
nodes--;
}
// print("front after loop : ");
print(front);
}

return head;
}

public void rotate(ListNode front, int k) {
int times = k/2;
int index = 0;
while (times > 0) {
swap(front, index, k);
index++;
times--;
}
// print("after 1 time of reverse the front" );
// print(front);
}

public void swap(ListNode front, int index, int k) {
int anti_index = k - index - 1;
ListNode head = front;
ListNode tail = front;
while (index > 0) {
head = head.next;
index--;
}

while (anti_index > 0) {
tail = tail.next;
anti_index--;
}

int temp = head.val;
head.val = tail.val;
tail.val = temp;
}

public void swap(ListNode head) {
int temp = head.val;
head.val = head.next.val;
head.next.val = temp;
}

// public void swap(ListNode tail, ListNode front) {
// int temp = tail.val;
// tail.val = front.val;
// front.val = temp;
// }

public static void main(String[] args) {
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
ListNode l6 = new ListNode(6);
ListNode l7 = new ListNode(7);
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;
l6.next = l7;
Solution sol = new Solution();
sol.print(l1);
sol.reverseKGroup(l1,2);
sol.print(l1);
}

public void print(ListNode head) {
if (head == null) {
System.out.println("The ListNode is null");
return;
}

while (head.next != null) {
System.out.print(head.val + "---->");
head = head.next;
}

System.out.println(head.val +"");
}

public void print(String s) {
System.out.println(s);
}
}

l*a2013-01-21 08:01

97 楼

写了个递归版本的。
ListNode *swapPairs(ListNode *head) {
if(head == NULL || head->next == NULL) return head;
ListNode * h1 = head;
ListNode* h4 = NULL;
if(h1->next && h1->next->next){
h4 = swapPairs(head->next->next);
}
ListNode * h2 = h1->next;
h1->next = h4;
h2->next = h1;
return h2;
}

h*n2013-01-21 08:01

98 楼

我的递归和非递归解法，贴在下面 OJ通过，还有每K个reverse那个，不过那个只有递
归版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
/*
//递归做法很简单，但是要切记前面几行的顺序，别放错了
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* next = cur->next;
if(next==NULL) return cur;

ListNode* nextnext = next->next;
next->next = cur;
cur->next = swapPairs(nextnext);
return next;
*/
ListNode* cur = head;
if(cur==NULL) return NULL;
ListNode* next = cur->next;
if(next == NULL) return cur;
ListNode* res = next;
ListNode* nextnext;
while(cur&&next)
{
nextnext = next->next;
next->next = cur;
if(nextnext)
{
if(nextnext->next)
{
cur->next = nextnext->next;
}
else
{
cur->next = nextnext;
}
//别忘了更新cur和next
cur=nextnext;
next = cur->next;
}
else
{
//这个else别忘了很重要，否则变成循环链表了
cur->next = NULL;
break;
}
}
return res;
}
};
Reverse in K-group
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!head) return NULL;
ListNode* cur = head;
int i = 0;
while(cur)
{
i++;
if(i>=k) break;
cur = cur->next;
}
if(ireturn head;

ListNode* pre = NULL;
ListNode* next;
cur = head;
i = k;
while(cur && i>0)
{
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
i--;
}

head->next = reverseKGroup(cur, k);
//这里要注意reverse的是pre
return pre;
}
};

h*n2013-01-21 08:01

99 楼

说实话，这个题也算基本题。不能怪他为难你，楼主还是加油吧啊

r*m2013-01-21 08:01

100 楼

我面2sigma电面的时候碰到了这个题，还好在OJ上写过了。
当时只给了电面的最后10分钟要求写出来。

h*n2013-01-21 08:01

101 楼

递归的话还是时间够的，一共就7-8行

【在 r*******m 的大作中提到】

: 我面2sigma电面的时候碰到了这个题，还好在OJ上写过了。
: 当时只给了电面的最后10分钟要求写出来。

r*m2013-01-21 08:01

102 楼

对，code是就那么短，也不一定要递归，定义指针的指针就很方便

【在 h****n 的大作中提到】

: 递归的话还是时间够的，一共就7-8行

w*x2013-01-21 08:01

103 楼

彩虹mm~~~~~~~

【在 r*******m 的大作中提到】

:
: 对，code是就那么短，也不一定要递归，定义指针的指针就很方便

n*e2013-01-21 08:01

104 楼

写个:P:
public void reversepair(Node head){
if(head == null) return;
Node second ==head.next;
Node first == head;
while(first != null && second !=null){
first.next = second.next;
second.next = first;
first = first.next;
second = first.next.next;
}
}
望大家指出问题~

n*e2013-01-21 08:01

105 楼

有个小问题这样写了以后head指的就不是头了，要把head改成head.next.

【在 n******e 的大作中提到】

: 写个:P:
: public void reversepair(Node head){
: if(head == null) return;
: Node second ==head.next;
: Node first == head;
: while(first != null && second !=null){
: first.next = second.next;
: second.next = first;
: first = first.next;
: second = first.next.next;

j*e2013-01-21 08:01

106 楼

我的解法，是一个普遍的k解法。在main里面把k改为2或者是面试官喜欢的k的值就ok。
希望大家指正。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NOT write main() function

int num = 1;
if (head == null) return null;
ListNode count = head;
while (count.next != null) {
num++;
count = count.next;
}
if (num/k <1)
return head;
int times = num/k;

ListNode front = head;
int nodes = 0;
while (times > 0) {
times--;
nodes = k;
rotate(front, k);
while (nodes > 0) {
front = front.next;
nodes--;
}
// print("front after loop : ");
print(front);
}

return head;
}

public void rotate(ListNode front, int k) {
int times = k/2;
int index = 0;
while (times > 0) {
swap(front, index, k);
index++;
times--;
}
// print("after 1 time of reverse the front" );
// print(front);
}

public void swap(ListNode front, int index, int k) {
int anti_index = k - index - 1;
ListNode head = front;
ListNode tail = front;
while (index > 0) {
head = head.next;
index--;
}

while (anti_index > 0) {
tail = tail.next;
anti_index--;
}

int temp = head.val;
head.val = tail.val;
tail.val = temp;
}

public void swap(ListNode head) {
int temp = head.val;
head.val = head.next.val;
head.next.val = temp;
}

// public void swap(ListNode tail, ListNode front) {
// int temp = tail.val;
// tail.val = front.val;
// front.val = temp;
// }

public static void main(String[] args) {
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
ListNode l6 = new ListNode(6);
ListNode l7 = new ListNode(7);
l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;
l5.next = l6;
l6.next = l7;
Solution sol = new Solution();
sol.print(l1);
sol.reverseKGroup(l1,2);
sol.print(l1);
}

public void print(ListNode head) {
if (head == null) {
System.out.println("The ListNode is null");
return;
}

while (head.next != null) {
System.out.print(head.val + "---->");
head = head.next;
}

System.out.println(head.val +"");
}

public void print(String s) {
System.out.println(s);
}
}

s*k2013-01-21 08:01

107 楼

写一个更通用的reverse m和N之间的
ListNode *reverseBetween(ListNode* head, int m, int n){
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i=1;
int j=1;
ListNode *start= head;
ListNode *end = head;
ListNode *tmp1= NULL;
ListNode *tmp2= NULL;

while(itmp1 = start;
start = start->next;
end = end->next;
i++;
j++;
}
tmp2 = start;

while(jtmp2 = start->next;
start->next = tmp2->next;
tmp2->next = end;
end = tmp2;
j++;
}

if(!tmp1){
head->next = start->next;
head = tmp2;
}else{
tmp1->next = end;
}

return head;
}

部。

【在 i**********e 的大作中提到】

: 应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
: 考点是注意链表为空，链表只有一个值的corner cases。
: 还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴和下一个 pair 头部。
: 要特别注意。
: 另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
: 给个例子：
: 链表： 1->2->3->4->5
: k = 2, 返回: 2->1->4->3->5
: k = 3, 返回: 3->2->1->4->5
: 这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴

a*n2013-01-21 08:01

108 楼

请教一下，，什么是OJ啊？？？

【在 r*******m 的大作中提到】

: 我面2sigma电面的时候碰到了这个题，还好在OJ上写过了。
: 当时只给了电面的最后10分钟要求写出来。

K*n2013-01-21 08:01

109 楼

痛吻

【在 a*****n 的大作中提到】

: 请教一下，，什么是OJ啊？？？

n*e2013-01-21 08:01

110 楼

这道题哪里能找到oj呢？

r*m2013-01-21 08:01

111 楼

OJ:
http://www.leetcode.com/onlinejudge
不是这道题么？
Swap Nodes in Pairs

r*m2013-01-21 08:01

112 楼

雅芝姐姐~~~~~~

【在 w****x 的大作中提到】

:
: 彩虹mm~~~~~~~

n*e2013-01-21 08:01

113 楼

写的有点问题，要加个temp保存上个循环的第二个值，oj通过492/536 milli secs。

【在 n******e 的大作中提到】

: 写个:P:
: public void reversepair(Node head){
: if(head == null) return;
: Node second ==head.next;
: Node first == head;
: while(first != null && second !=null){
: first.next = second.next;
: second.next = first;
: first = first.next;
: second = first.next.next;

n*e2013-01-21 08:01

114 楼

多谢彩虹姐~

【在 r*******m 的大作中提到】

: OJ:
: http://www.leetcode.com/onlinejudge
: 不是这道题么？
: Swap Nodes in Pairs

r*y2013-01-21 08:01

115 楼

singly-linked list
不是用铅笔+橡皮

【在 S******0 的大作中提到】

: 直接交换数字

e*s2013-01-21 08:01

116 楼

楼主能不能透露一下，其他的题目？

f*o2013-01-21 08:01

117 楼

你水平不行，不怪烙印

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个

w*x2013-01-21 08:01

118 楼

aglee

【在 f*o 的大作中提到】

: 你水平不行，不怪烙印

s*f2013-01-21 08:01

119 楼

这个可能老中也会挂你呵呵

【在 h********w 的大作中提到】

: 总共面了5个人，4点结束，没见到中国人。估计是栽在第二个烙印手里了。
: 很不nice, 问了个reverse each pair of node in singly-linked list
: 就是1->2->3->4->5
: 得到2->1->4->3->5
: 我说stack做吧，他就让我做了，刚开始写的有问题，但后来我fix了，解法比较麻烦，
: 他看了不高兴。说是用俩个指针做就行。说实话，我现在也没想明白，后来回来后我用
: recursion写出来了。
: 谁知道给个只用reference, 或pointer来解个