Bloomberg 电面

xinwei

问了背景 熟悉的语言，答Java，说可以用Java做题。然后问熟悉什么数据结构，答链表 树 hashmap什么的。。然后就出了俩链表题。。

1 Reversely print a Linked List
- ^9 l6 S- g2 e, g- ?递归做或Stack存下，说思路后，让任意挑一种实现

2 Swap Two Nodes in a Linked List
给出要swap的两个nodes的index， 如pos1=1，pos2=3,
  t3 Y& z/ j0 f5 p4 U6 A假设pos1 pos2 都是valid，且pos1< pos2。
2 I4 M1 C6 F1 X0 g) z0 K0 {4 U举例：链表开始时长这样： 0->1->2->3->4->5-null，
swap后变成： 0->3 >2->1->4->5-null


! l( B! p/ u2 ?# }corner case:
# B  g$ g! T; ^& A6 K% @" a（1）表空 || 只有一个node || pos1=pos2： 不用swap, 直接返回
（2）pos1=0 : 最开始时加个dummy node
2 c! I1 A* ?9 U7 \1 K! H$ |（3）pos1+1=pos2 : 直接swap这两个相邻的节点

% h/ B2 P0 j  Q8 p% |& L
/ j2 c( p  l- U  ]一般case:
根据pos1和pos2， 遍历链表，找到这俩index所指示的node
. Q0 V: ]( @3 k: S8 m3 {弱弱地用了6个指针，分别指向pos1、pos2 的前面，当前和后面的节点，做swap。。
" w+ P! g& Q/ \
6 K$ e+ u; |* L8 q& J# y
求解有没有更简洁的做法，或者少用点指针。。
2 G' e9 i' L4 B6 x% G' a1 Z3 b9 d
! U3 q6 [6 ]8 u1 S% |) S$ f面试时做得不好，估计跪了，o(︶︿︶)o ，伤心。。求积分。。

Sophia

Thanks for your sharing~~~