链表相干的口试题型总结及其个别实现
对指针的把握程度，是衡量一个法度员的根蒂根基功是否扎实的首要考量标准。而数据布局中的链表、二叉树等根蒂根基数据布局，是查核指针的利器。本文稍微总结了下链表的首要考点，以备将来的求职。
说在前面的重视事项
起首，涉及到指针的编程，对于指针有效性的断定不成忽视，代码中必然要有对NULL指针的断定，如许代码才加倍的鲁棒。
其次，若对链表进行插入，删除操纵，必然要重视更新head指针（和tail指针）的指向。
最后，我们定义结点的数据布局为：
struct Node{
int datum;
Node
next;
};
先总结下我的心得
起首，若是题目对空间错杂度没有什么请求，可以鉴戒hash，额外的数组等，将题目简化
其次，可以应用快慢指针的思惟，设置两个指针，一个指针走得快些或先走几步，就可以或许很好的解决大多半题目。
再者，对于指针的接见操纵，必然要警惕再警惕，必然要确认有效才干持续接见。
最后，涉及到插入，删除操纵，函数中传入的指针参数要设置成 Node， 如许才干进行批改操纵。
常考的题型
对于链表， 首要查核以下几类项目组：
一、查询断定类
- 断定两链表是否订交， 若订交，返回第一个订交结点
- 断定链表是否有环
- 求链表的倒数第 K 个数
二、操纵类
- 链表排序
- 链表插入
- 链表删除结点
- 若给定欲删除的结点指针，如安在O（1）时候内删除？
- 有序链表归并
- 错杂链表复制
题目解析及求解
1.1. 两链表（无环）订交的剖断
思路一：
尾地址剖断法。常规的断定办法是断定两链表的
最后一个结点地址是否雷同。具体做法是先遍历list1， 保存最后一个结点的地址end1；再遍历list2到最后一个结点，断定地址是否便是end1。
时候错杂度为O（len1+len2）， 空间错杂度为 O（1）。
1 bool cross_tail_compare（Node h1， Node h2）
2 {
3 if（h1 == NULL || h2 == NULL）{
4 return NULL;
5 }
6 Node p = h1;
7 while（p->next!=NULL）{
8 p = p->next;
9 }
10 Node q = h2;
11 while（q->next!=NULL）{
12 q = q->next;
13 }
14 return （p == q）;
15 }
View Code
思路二：hash地址法。凡是若容许应用hash的话，可以或许快速有效的解决。 这里，我们遍历list1， 将每个结点的地址hash；再遍历list2，断定结点地址是否呈如今hash表中。时候错杂度为O（len1+len2）， 空间错杂度为O（len1）; 这里，固然时候错杂度未降落，同时增长了空间错杂度，然则却能很好的解决第1个公共结点题目。算是一种抵偿。
思路三：链接成环法。参考下面图3。起首，先将第一个链表的最后一个结点链接到第二个结点的头，然后断定是否有环，如有环，则申明两个链表存在公共结点。
1.2. 链表是否有环的剖断
思路一：
快慢指针法. 我们在用快fast， slow两指针指向链表头，fast指针一次跨两步， slow指针一次跨一步，有环的前提为fast==slow ！= NULL 。
1 Node fastinCircle（Node head）
2 {
3 if（head == NULL）
4 return NULL;
5 Node fast = head;
6 Node slow = head;
7 while（（fast!=NULL） && （fast->next != NULL） && （slow!=NULL））{
8 fast = fast->next->next;
9 slow = slow->next;
10 if（fast == slow） break;
11 }
12 if（（fast == NULL） || （fast->next == NULL） || （fast != slow）） return NULL;
13 return fast;
14 }
View Code 思路二： hash地址法。遍历链表，将地址hash进来，若NULL了，则申明无环，若存在雷同的地址，则申明有环。 且能获得第一个入环的点。时候错杂度为O（len1）， 空间错杂度为O（len1）。
1.3. 寻找两链表的第一个公共结点
思路一：hash地址法。经由过程1.1的解析，我们可以或许用hash的办法快速获得第一个公共的结点。
思路二：
首尾对齐法。若采取尾地址剖断法，我们可以或许获得最后一个公共结点，那么回溯N步同时断定地址是否相等，就能获得第一个公共结点了。可惜是单链表，没有prev指针，然则这个思惟启发了我们，若是两个链表尾对齐了，那么对长链表先next X 步，使头部也对齐，那么，第一个雷同的地址点，就是第一个公共结点了。按照 图3， 我们可以看出，长链表先走X=（lenMax-lenMin）步后，那么，他们将同时递增到first common 点。时候错杂度为O（len1+len2+x）， 空间错杂度为O（1）。
Node cross_first（Node h1， Node h2）
{
if（h1==NULL || h2==NULL）{
return NULL;
}
Node p = h1;
int s1 = 0;
while（p->next != NULL）{
++s1;
p = p->next;
}
Node q = h2;
int s2 = 0;
while（q->next != NULL）{
++s2;
q = q->next;
}
if（p != q）
return NULL;
p = h1;
q = h2;
int prestep = static_cast<int>（abs（s1-s2））;
if（s1>s2）{
while（prestep--）{
p = p->next;
}
}else{
while（prestep--）{
q = q->next;
}
}
while（p != q）{
p = p->next;
q = q->next;
}
return p;
}
思路三：链接成环法（也是求环的进口点的解法）。将链表1的尾结点链接到链表2的第一个结点，然后调用快慢指针法断定是否有环。然后保存相遇点，同时slow指针从头开端，步长为1递增；fast指针从相遇点开端，步长为1递增，他们再一次的相遇点，则是第一个公共结点。
数学推导如下：
先假设链表长 L， 入环前结点数 b， 环内结点 r， slow指针走了 s 步相遇， 相遇点为环内 x 步， 则 fast 指针走了 2s 步， 且相遇点前fast已近走了n（n>=1） 圈。 则有：
s+nr = 2s
s = nr
s = b + x
r = L - b;
b + x = nr = （n-1）r +r = （n-1）r + L - b
b = （n-1）r + L-b-x
这里，L-b-x 便是相遇点到环结尾的长度，b 为开首到环进口的长度。是以，在链表头和相遇点各设置一个指针，持续走 b 步，就必然能相遇。
Node cross_first_by_circle（Node h1， Node h2）
{
if（h1 == NULL || h2 == NULL） return NULL;
Node p = h1;
while（p->next != NULL）{
p = p->next;
}
Node holdh1 = p;
p->next = h2;
Node fast = NULL;
fast = fastinCircle（h1）;
if（fast == NULL） return NULL;
Node slow = h1;
while（fast != slow）{
fast = fast->next;
slow = slow->next;
}
p->next = NULL;
return fast;
}
参考材料：
http://www.cnblogs.com/gw811/archive/2012/10/28/2743182.html
http://wenku.baidu.com/view/299c440cf78a6529647d536b.html
《剑指offer》
1.4 求链表的倒数第K个数
有了前面首尾对齐法和快慢指针的思惟，我们是不是能启发到怎么求倒数第K个数呢？
思路一： 若是双向链表，则很简单，从尾端往回走K步就行。
思路二： 若是单链表，先遍历获得链表的长度，然后逆推出要到倒数k地位，则要走 n-k+1步；
思路三：
很简单，设置两个指针，一个指针从从头先走k-1步，别的个指针再从头开端，那么，当第一个指针达到结尾时，别的个指针正好达到倒数第K个结点。
Node backK（Node head， int k）
{
if（head == NULL || k <= 0） return NULL;
Node p = head;
for（int i=0; i<k-1; ++i）{
if（p->next == NULL） return NULL;
p = p->next;
}
Node knode = head;
while（p->next != NULL）{
p = p->next;
knode = knode->next;
}
return knode;
}
归纳法证实：
若k=1: k-1 = 0， 两个指针同步运行，成立。
若k=x; k-1 = x-1; 第一个指针持续走 n-x步达到最后一个结点， 第二个指针走 （n-x） 步后，处于倒数 n-（n-x）=x 的地位，成立。
这里的重视事项是： 若链表长度小于k怎么办？ 输入的是空链表怎么办？若输入k=0， 则k-1步导致溢出怎么办？是以，写好一个好的代码是要推敲很多身分的。
2.1 链表排序
对链表排序，想下似乎挺简单的，实际上是很富有挑衅性的。这里我们以单链表为例。
思路一： 若是空间很是充裕的话，我们完全可以鉴戒STL中对deque进行排序时辰的做法，先将元素赋值到vector中，排序后再拷贝回deque。 做法也是一样的，遍历链表，把每个元素存入到一个新的数组中，然后对该数组排序（默认应用快排），然后再拷贝回链表（只批改卫星数据）。时候错杂度为O（n+nlgn+n） = O（nlgn）， 空间错杂度为O（n）；
思路二： 单链表，只能前向移动，我们推敲到简单的排序办法必须是相邻进行斗劲的，合适前提的有插入排序，冒泡排序，甚至，希尔排序也是可以的。同时，排序算法内部的轮回也必须是前向移动才行。
2.2 链表插入
对于链表插入操纵，分为头插法和尾插法。 若是排序好的链表插入，还要定位到响应的地位。
1 Node _front（Node head， int value）
2 {
3 if（head == NULL）
4 return NULL;
5 if（head == NULL）{
6 head = new Node（value）;
7 }else{
8 Node p = new Node（value）;
9 p->next = head;
10 head = p;
11 }
12 return head;
13 }
14 Node _comp（Node head， int value）
15 {
16 if （head == NULL）
17 return NULL;
18 Node in;
19 if （head == NULL） {
20 in = new Node（value）;
21 head = in;
22 }else{
23 in = new Node（value）;
24 if（（head）->datum > value）{
25 _front （head， value）;
26 }else{
27 Node p = head;
28 Node n = （head）->next;
29 while（ n != NULL && n->datum < value）{
30 p = n;
31 n = n->next;
32 }
33 p->next = in;
34 in->next = n;
35 }
36 }
37 return in;
38 }
2.3 链表删除某一节点
对于删除操纵，简单的来说，就是两个指针，一前一后，后的一个达到删除点后，操纵就很简单了。还有个办法，见2.4.
2.4 单位时候内删除节点（节点指针给定）
对于这个，一般凡是的做法是采取2.3的做法，然则这个时候错杂度为O（n）。 可以参考下<剑指offer>中介绍的办法，我们先画图来说下：
图4的上半项目组是我们凡是（2.3）的做法，须要前一个指针帮助删除；
图4下半项目组的删除，就不须要了。做法如下：
起首来个帮助指针q指向下一个结点。 将q的数据域赋给cur， 然后更新cur.next， 最后删除q。 如许，就能在O（1）的时候内删除结点了。
1 void delNode（Node head， Node n）
2 {
3 if（head == NULL || head == NULL || n == NULL）
4 return;
5 if（n->next != NULL）{ // 删除的不是尾结点;
6 Node tmp = n->next;
7 n->datum = tmp->datum;
8 n->next = tmp->next;
9 tmp;
10 tmp = NULL;
11 }else if（head == n）{ // 仅有一个结点
12 n;
13 head = NULL;
14 }else{ // 删除尾结点
15 Node p = head;
16 while（p->next != n）{
17 p = p->next;
18 }
19 p->next = NULL;
20 n;
21 n = NULL;
22 }
23 }
2.5 有序链表归并
这个可以参考下STL中的接合函数的写法。
2.6 错杂链表复制
参考下<剑指offer>
测试函数：
1 void show（const Node head， const Node end = NULL）
2 {
3 if（head == end） return;
4 const Node p = head;
5 while（p != end）{
6 cout << p->datum << --> ;
7 p = p->next;
8 }
9 if（end == NULL）
10 cout << NULL << endl;
11 else{
12 cout << end->datum << endl;
13 }
14 }
打印函数
1 ＃include myslist.h
2 ＃include <iostream>
3 using namespace std;
4 int main（）
5 {
6 Node head1 = NULL;
7 _comp （&head1， 1）;
8 _comp （&head1， 2）;
9 _comp （&head1， 3）;
10 _comp （&head1， 7）;
11 _comp （&head1， 15）;
12 Node head2 = _comp （&head1，6）;
13 _front（&head2，5）;
14 _front（&head2，4）;
15 show（head1）;
16 show（head2）;
17 cout << Is cross？ << cross_tail_compare （head1，head2） << endl;
18 cout << The first cross point by cross_first: << cross_first （head1，head2）->datum << endl;
19 cout << The first cross point by cross_first_circle: << cross_first_by_circle （head1，head2）->datum << endl;
20 cout << back 5s node of head1 is: << backK （head1，5）->datum << endl;
21 Node pp = fastinCircle （head2）;
22 if（pp == NULL）{
23 cout << No circle << endl;
24 }else{
25 cout << circle << endl;
26 }
27 cout << -----------Test Circle--------------- << endl;
28 Node head3 = NULL;
29 _comp （&head3， 1）;
30 _comp （&head3， 2）;
31 Node circin = _comp （&head3， 3）;
32 _comp （&head3， 7）;
33 Node tail = _comp （&head3， 15）;
34 tail->next = circin;
35 show（head3，tail）;
36 show（tail，tail->next）;
37 pp = fastinCircle（head3）;
38 if（pp == NULL）{
39 cout << No circle << endl;
40 }else{
41 cout << circle << endl;
42 }
43 return 0;
44 }
思路一： 快慢指针法. 我们在用快fast， slow两指针指向链表头，fast指针一次跨两步， slow指针一次跨一步，有环的前提为fast==slow ！= NULL 。
思路二：首尾对齐法。若采取尾地址剖断法，我们可以或许获得最后一个公共结点，那么回溯N步同时断定地址是否相等，就能获得第一个公共结点了。可惜是单链表，没有prev指针，然则这个思惟启发了我们，若是两个链表尾对齐了，那么对长链表先next X 步，使头部也对齐，那么，第一个雷同的地址点，就是第一个公共结点了。按照 图3， 我们可以看出，长链表先走X=（lenMax-lenMin）步后，那么，他们将同时递增到first common 点。时候错杂度为O（len1+len2+x）， 空间错杂度为O（1）。
