i*********h
发帖数: 49 | 1 【总结】Java 搞定链表-面试常考题目精选
面试大总结之链表：
一、OverView:
链表是面试中常考的，本文参考了其它一些文章，加上小编的自己总结，基本每个算法
都测试并优化过。
算法大全（1）单链表 中还有一些链表题目，将来也会整理进来。这些题目虽然简单，
但如果能毫无BUG地写出，定能让面试官司对您印象分大增。
小亮点是：主页君用Recursion 和 Iterator 各写了一次所有题目，这样就算遇到不熟
悉的写法，我们也都可以运用自如。
二、代码
以下是原文和代码：
http://weibo.com/3948019741/BseJ6ukI3
三、代码目录：
1. 求单链表中结点的个数:
getListLength
2. 将单链表反转:
reverseList（遍历），reverseListRec（递归）
3. 查找单链表中的倒数第K个节点（k > 0）:
reGetKthNode
4. 查找单链表的中间结点:
getMiddleNode
5. 从尾到头打印单链表:
reversePr... 阅读全帖 |
|
|
h*****7
发帖数: 103 | 3 中文OJ上有的：
给定一个单链表，链表除了包含next指针外，还包含一个random指针，该指针指向链表
中某个结点。
请复制链表到一个新的链表，random指针需要指向新链表中对应的结点。比如原链表某
个结点random指针指向第2个结点，那么新结点的random指针也要指向到新链表的第2个
结点。
要求是不用extra space，就是除了被复制的链表外，不允许用哈希之类的映射表了吧
，没想出怎么搞，请大牛指点，thanks !! |
|
j**l
发帖数: 2911 | 4 http://www.mitbbs.com/article_t1/JobHunting/31563337_0_1.html
三江口内，风浪不息，铁索连舟，如履平地。
这是小尾羊同学Google最终面的一道经典题目
核心思想就是，先合后分。
先平凡复制整个链表，不考虑random指针。
充分利用random指针和next指针，把原始链表和复制的链表这两个链表关联起来。传说
中有两种连接法：一种是串成长度为2倍的新链表(类似一串珍珠)，另一种是两个平行
但在竖直方向对应节点相连的链表（类似横着的梯子)
不管哪种连法，都可以方便的给random指针赋值。
然后不要忘记把两个链表的关联断开，成为两个一样的独立链表。 |
|
g****n
发帖数: 431 | 5 这帖子里讨论出了2种方法，我再加一种：
因为每个Node里的data是int，size跟一个pointer一样，所以首先把原链表的所有data
读出来，
按顺序存到一个array里。然后复制链表，同时把原链表的每个node里的data用作指针
，指向复制出
的新链表中的对应节点。这样原链表和新链表的每个节点都有了单向对应关系，用这个
关系可以把新链
表中的another指针解决。最后，把array里的data按顺序写到原链表中。
方法跟帖子里的“梯子法“类似，区别在于使用了更少的额外空间。 |
|
b****n
发帖数: 84 | 6 如果一个链表是用如下的数据
struct Node
{
int data;
Node* next;
Node* another;
};
实现
Node* duplicateList(Node* list)
//
// input: 单链接链表，node->another指向这个链表中的一个任意节点 nodes
within the list
// output: 一个和原来链表有相同结构的新的链表,其中的节点不指向原来的链表
//
能想到的算法是用hash table，O(N), 如果不用额外空间的话, O(N^2)
还有什么更好的办法么? |
|
r****o
发帖数: 1950 | 7 【 以下文字转载自 JobHunting 讨论区 】
发信人: roufoo (五经勤向窗前读), 信区: JobHunting
标 题: 单链表构成的循环链表比单链表有什么优势?
发信站: BBS 未名空间站 (Sat Jun 12 15:48:49 2010, 美东)
前天一个面试，别的都答出来了，就这个题卡出了，
单链表构成的循环链表 比 单链表有什么优势? 或者说，什么情况下用循环链表比用单
链表更好? |
|
j*****n
发帖数: 1545 | 8 【 以下文字转载自 CS 讨论区 】
发信人: jetchen (飞机), 信区: CS
标 题: 问一个链表方面的算法问题
发信站: BBS 未名空间站 (Sun Jan 24 00:08:52 2010, 美东)
小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
有一个循环链表 a->d->b->c->e->....->a
每一个节点都是一个整数，且不重复(除了首尾节点外)。
现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
我想重新把链表建立起来，应该用什么样的算法?
谢谢. |
|
j********x
发帖数: 2330 | 9 如下：
第一次遍历原链表，复制节点，并将复制节点的another指针指向其在原链表中的对应
节点；
将复制链表的节点next指针指向其在原链表中的对应节点的下一个节点；
将原链表节点的next指针指向对应的复制节点；
第二次遍历，对每个复制节点，首先记录其对应的原节点（在another里）；
恢复复制节点的another（通过原节点的another-》next）；
第三次遍历，因为现在实际上原节点指向复制节点，复制节点的next指向原节点的下一
个节点；如果原节点顺序为：1 2 3 4 5 ... 复制节点为1' 2' 3' 4' 5' ...；
现在实际的顺序为：1 1' 2 2' 3 3' 4 4' 5 5' ...，很容易看出可已通过next恢复原
节点和复制节点的next指针。
常数空间，线性时间 |
|
r****o
发帖数: 1950 | 10 前天一个面试，别的都答出来了，就这个题卡出了，
单链表构成的循环链表 比 单链表有什么优势? 或者说，什么情况下用循环链表比用单
链表更好? |
|
r**d
发帖数: 316 | 11 可以
基本思想
1：显然,空链表和单节点链表直接返回
2：取下第一个节点
3：递归处理余下的链表，需要将逆转后的链表的尾传出来
4：把第一个节点连到队尾。 |
|
j*****n
发帖数: 1545 | 12 小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
有一个循环链表 a->d->b->c->e->....->a
每一个节点都是一个整数，且不重复(除了首尾节点外)。
现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,....
我想重新把链表建立起来，应该用什么样的算法?
谢谢. |
|
h****n
发帖数: 1093 | 13 1.写一个int转成链表的函数 链表每个节点存一个digit，要注意表示负数的情况
2.写一个对两个数字表示链表的加法函数，要考虑到负数情况 |
|
w*****z
发帖数: 6 | 14 我在做一个Qt的课题，需要链表操作界面化。算法这部分只是普通的C++，但是节点不
能够用struct，一定要用class。我在node.h中声明了两个指针,*previous和*next。链
表里面有Node* first和Node* current。请问我在链表的Deconstrucotr(LinkedList::
~LinkedList())中应该写些什么？我写的是：
C/C++ code
Node::~Node() {
previous = NULL;
next = NULL;
}
C/C++ code
LinkedList::~LinkedList() {
current = first;
while(current!=NULL){
first = current->next;
delete current;
current = NULL;
current = first;
}
current = NULL;
first = NULL;
}
然后试运行时Win |
|
w*****z
发帖数: 6 | 15 我在做一个Qt的课题，需要链表操作界面化。算法这部分只是普通的C++，但是节点不
能够用struct，一定要用class。我在node.h中声明了两个指针,*previous和*next。链
表里面有Node* first和Node* current。请问我在链表的Deconstrucotr(LinkedList::
~LinkedList())中应该写些什么？我写的是：
C/C++ code
Node::~Node() {
previous = NULL;
next = NULL;
}
C/C++ code
LinkedList::~LinkedList() {
current = first;
while(current!=NULL){
first = current->next;
delete current;
current = NULL;
current = first;
}
current = NULL;
first = NULL;
}
然后试运行时Win |
|
j*****n
发帖数: 1545 | 16 再问个问题，
如果每个cell里面是没有方向的，只考虑连接情况
就是说cell可以是这样的， a-d, c-e, c-b,...,d-b,....
我想重新把链表建立起来，对应的链表还是 adbce....
还能用hash么？
谢谢 |
|
j*****n
发帖数: 1545 | 17 我想了这个简单办法,
假设 节点是从 0-10,
建一个n*2的矩阵, 先遍历所有cell，假设i-j在一个cell里, 则把矩阵的第i行的第0或
者第1列(看哪列是空的)置成j. 这样就把这个矩阵都能填满.
然后把这个矩阵遍历一遍, 就能把这个链表建立起来了。
比如 链表是 0-5-2-3-9,... 我先把 0 和 5 push到link里面去, 然后去看matrix第5
行, 把非0的那个entry 2找出来，push 到 link里面去； 然后去看matrix第2行把非5
的那个entry 3 找出来, .....
这个办法算有效的吗? |
|
R***Z
发帖数: 1167 | 18 今天和一个老美一起电面了一个在M呆了3年的人。这个人连快速排序都解释不清，也说
不清运行时间是多少。这也算了，就算你好久不用不记得。但后来给他一简单的反转链
表，他花了30分钟都写不出来。看了版上平时讨论的题,M没那么好进吧？而且我记得反
转链表就是以前从M出来的题啊。真搞不懂他是怎么进去的。 |
|
c******m
发帖数: 491 | 19 把链表convert成integer， 做完加法之后再convert成链表 |
|
A******g
发帖数: 612 | 20 链表没有random access，swap value的话要jump back and forth， 复杂度大概是O(N
^2)。 recursion的话等于把每个节点的地址都存到stack里，所以时间是O(N),空间也
是O(N)。 话说回来，如果先用一个array把每个链表节点的地址存起来，那么既可以反
转next，也可以swap value, 都是O(N)，和recursion一样了，code也挺好写。
谢谢你给的灵感！ 对这题的认识又加深了。
nodes |
|
t*********3
发帖数: 87 | 21 原链表节点数据结构是
class node{
int value;
node next;
node random;
}
假设原链表是：
a-b-c
然后复制每个节点到自己的后面（不许额外存储空间，O(n)时间）：
a-a'-b-b'-c-c'
然后对于每个新复制的带'号节点复制random指针。以a'为例：
a'.random = a.random.next; |
|
|
l*******t
发帖数: 79 | 23 leetcode新题是两个链表相交找交点，最近看面经有follow up是多个链表相交找第一
个交点。小弟不才求高人指点，谢过大家！ |
|
t*8
发帖数: 14 | 24 1.翻转两个链表，然后比较
2.分别把两个链表的节点放到两个stack里面，然后同时pop这个stack比较
还有别的办法吗？ |
|
j********l
发帖数: 325 | 25 链表题目用 dummy head更不容易出错，尤其是涉及到第一个结点会变化的情况。
有一个面试，面试官让我用了三种方法来反转链表，当然更多的是探讨性质，看看都有
哪些玩法 |
|
p****a
发帖数: 447 | 26 最喜欢链表了，基本只有链表有把握，别的都拿不准... |
|
I*******x
发帖数: 69 | 27 这几天刷题，全部是链表的题，感觉链表对我来说稍微容易一些，其它的我很容易晕。 |
|
r****e
发帖数: 42 | 28 单向链表的数据结构查找是否都是从头开始？如果某个数据位于链表后部，查找起来
很花时间，有什么好办法快速找到这个数据？各位高手请帮忙！！！！
呼唤高手！！！！！！！ |
|
b***y
发帖数: 2799 | 29 ☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Fri Jul 18 22:00:22 2008) 提到:
一个链表中有环，如何求解这个环的起始位置。
网上已经有人给出答案，就是用2个指针，p=p->next, q=q->next->next，找到它们相
遇的位置，再求解这个环长度Y,从起点head到这个相遇位置长度L，
然后另2个指针，1个从head出发，1个从距离相遇位置Y-L%Y位置出发，直到这2个指针
相遇，此时就是环在链表中的起始地址。
现在我还是不懂得，这个L%Y是如何来的。
请指点一下。
☆─────────────────────────────────────☆
goodbug (好虫) 于 (Fri Jul 18 22:12:19 2008) 提到:
这么复杂干啥？先找出环，这标准的跳1跳2就可以弄出来，转一圈记录长度。
然后环上设一指针静止，另一指针从头上走，碰到为止，记录步数。
如此转一整圈，最小值就是起始位置。
时间复杂度都是O(N^2)
☆────────────── |
|
w*********a
发帖数: 9279 | 30 【 以下文字转载自 CS 讨论区 】
发信人: wugongpanda (Sela'ma ashal'anore!), 信区: CS
标 题: 深受memory fragmentation毒害。少用长链表
发信站: BBS 未名空间站 (Mon Feb 25 11:46:31 2013, 美东)
c++分配内存的方法确实不好。分配内存效率低。
尤其是长链表，一旦free之后，fragmentation太多。严重影响效率。
而且关键是不cache friendly.
从这个意义上说，reference counting 也有这个不足。 garbage collection要好得多
。 |
|
f***c
发帖数: 338 | 31 在网上看到，基本都是遍历都给定节点，然后将下一个节点指向当前的前一个节点。
大多数的例子，都是对int的链表，所以memory不是问题。如果链表的内容是一个很大
的数据结构，是否需要释放该节点的内存？如何释放？
请专家指点。
谢谢。
这里是我的一个实现。
"delete cur"试图释放节点内存，似乎多此一举，因为这里cur是个auto变量，函数返
回时自动释放内存。
void del(Node *&head, int n) {
Node *cur = head, *pre=NULL;
while (cur) {
if (n == cur->val) {
if (cur == head) {
/* if the node is the head*/
head = head->next;
return;
}
pre->next = cur->next; //next -> pre
... 阅读全帖 |
|
d****i
发帖数: 4809 | 32 这个和节点数据是整数型还是复杂类型无关，之所以一定需要delete cur，是因为你创
建这个链表的时候，这个待删除的节点是这样创建的：Node *cur = new Node;所以
delete这行这个相当于是在把这个节点从链表中拿走以后释放这个节点所占用的内存。 |
|
j**l
发帖数: 2911 | 33 一个好处是可以用来解决约瑟夫环...
另外，循环链表无所谓表头在那里
另外如果你能说出循环数组有什么优势也行，循环数组适合当队列用，比普通数组好。 |
|
O******i
发帖数: 269 | 34 5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
版上最近刚讨论过。递归或者iterative都有。
有要求必须改动节点的指针指向而不准改动节点的值么？（in place逆转整个链表就是
改动指针指向）
还是可以自由交换每个节点的值？（狸猫换太子, 单链表只知道一个指向某中间节点的
指针要删除该节点就用了此手法) |
|
h**k
发帖数: 3368 | 35 能，只要你cell里记录的顺序是按照实际链表指向的顺序记录的。 |
|
h**k
发帖数: 3368 | 36 可以，稍微复杂一些。每个cell要分别按照其中的node存一次。比如cell: c-a，既要存
到node c这一项，也要存到node a这一项。而且重构的链表可能和原来的方向相反。 |
|
Z*****Z
发帖数: 723 | 37 一个是给了一组《id，parent id》对，如何重构出原来的树。
一个是给了一组《id，parent id》对，并且已知构建出来的一定是个链表，怎么做。 |
|
j***n
发帖数: 301 | 38 一个linked-list，每个节点除了正常next指针外，还有一个extra指针，这个指针可以
指向链表中的任一节点，不同的extra指针可以指向同一个节点，extra指针也可能形成
loop。问怎么复制这个结构。 |
|
j**l
发帖数: 2911 | 39 要求in place就地转换
１．从BST转为sorted doubly-linked list可以用类似中序遍历的递归方法做，结果唯
一。
２．那么反过来，从sorted doubly-linked list转换为一棵BST, 结果不唯一，该如何
做才能尽可能的保证BST是平衡的呢(minimal height)？如果是从sorted array转为最
小高度的平衡BST，有类似binary search的思想。对双向链表，有什么好的思路？
1的白板代码如下
void TreeToList(Tree* root, Tree* &head, Tree* &tail)
{
// This is a very special case
if (root == NULL)
{
head = NULL;
tail = NULL;
return;
}
Tree* temp_head;
Tree* temp_tail;
if (root->left != NULL)
{
|
|
d*****t
发帖数: 41 | 40 新链表是unique的节点还是duplicated节点组成的？ |
|
f********e
发帖数: 166 | 41 板上大牛能不能给贴个代码啊，反转链表用递归咋写啊？谢谢啊谢谢 |
|
f*******t
发帖数: 7549 | 42 有的，原链表的head的next指针需要通过这条语句设成NULL，中间的node倒无所谓。 |
|
c*******r
发帖数: 309 | 43 问了一个链表，1－>2->3->4->5, 每两个交换，2－>1->4->3->5,如果单数
情况返回最后一个, 要求interative和recursive.
实在不会写. 在java里用linkedlist的libirary, node怎么表示啊?
有人能否上个java的代码啊......
linkedlist把我搞晕了 |
|
l******d
发帖数: 530 | 44 为什么我会写反转链表但是MS不要我，为什么为什么 |
|
c*******u
发帖数: 1657 | 45 我总感觉像FLAG这种狂考算法的面试，有点像以前的八股文了，大家都去背，去钻，实
际工作中又能用到多少呢？ 就像以前考八股文能拿状元的真是最有才华的吗？
人家做web browser control的，平时可能用不到反转什么链表，只是人家没看过这种
题目而已，人家花上2个月钻研一下八股文，一样什么都能写
术业有专攻，也许人家对web performance有着比较好的理解和经验，问你怎么提高web
performance的东西，你没经验你照样也答不上来，所以没必要嘲笑别人 |
|
A*****i
发帖数: 3587 | 46 说实话翻转链表这题我知道两年了，来来回回做了也不下10遍了，但是现在看到这题，
要想不用递归还得想老久还不一定是bug free.
有时候确实挺邪门，有的问题自己看起来很难理解，而且长期都觉得难，虽然知道答案
但是还是觉得难。
太菜了估计 |
|
a********x
发帖数: 1502 | 47 我觉得也不见得是他水平不行吧，只不过反转链表这种东西我平时写project确实不太
遇得到。
这东西我觉得就实用程度可能还不如动态规划和网络流这类得算法呢。 |
|
e****e
发帖数: 418 | 48 我的理解：
-123 表示成链表：'-' --> '1'--> '2' --> '3' |
|
l**h
发帖数: 893 | 49 之前看到面经:"n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min
heap的方法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开
销，写了代码。"
min heap的方法容易解释，但是怎么O(1) space合并而时间效率和min heap一样呢？ |
|
