归纳链表题的另一类解法

经初步研究发现，所有公司的面试中链表是必考的内容，所以找了些题整理了一下。链表的题型虽然千变万化，很难捉摸，但其中还是有一些共性问题的，在这里选几道简单总结一下。

 

1. 如何找出单链表的中间节点？

你可以先遍历一次，数一下结点个数。然后结点个数除以2再数一遍。这样做是可以的，但这样的解法与本文的主题无关。本文是要介绍“两个变量”的解法。

1) 定义两个指针fast和slow指向链表头；

2) 在循环体中，fast每次向后移动两个结点，slow移动结点；

3) 当fast到达链表尾时，slow正好位于中间位置。

 

 

2．如何找出单链表中倒数第k个节点？

如果是数组就简单了，直接长度除以2取数就可以了。如果是双向链表也行，定义两个指针，一个从头走，一个从尾走，两个相遇点就是中点。但如果是单链表呢，怎么办？



1) 定义两个指针fast和slow指向链表头；

2) 首先，fast向后移动k个结点；

3) 在循环体中，fast和slow每次向后移动一个结点；

4) 当fast到达链表尾时，slow正好位于倒数第k个位置。




3．如何判断单链表中是否有环？



这道题可以用反转法来解决，但按照本文的主题要推荐的是下面这个解法：

1) 定义两个指针fast和slow指向链表头；

2) 在循环体中，fast每次向后移动两个结点，slow每次向后移动一个结点；

3) 如果没有环的话，fast会抵达链表尾，否则fast会追上slow；



4．如何判断两个链表是否交叉？

如果你把两个单链表交叉想成了X形那你就废了。单链表交叉怎么会是X形，应该是Y形才对呀，这下简单了：


1) 定义两个指针a和b分别指向了两个链表头A，B；

2) 遍历A，使a指向尾结点；

3) 遍历B，使b指向尾结点；

4) 如果a==b则交叉，否则不交叉。



5．如何找出两个交叉链表的交叉节点？





两个指针分别指向两个表头，然后依次后移，行么？能相遇在交叉点么？当然不行啦，只有当两个指针到交叉点的距离相同时，依次后移才会在交叉点相遇：

1) 定义两个指针a和b分别指向了两个链表头A，B；

2) 遍历A，得到链表长度La；

3) 遍历B，得到链表长度Lb；

4) 再使指针a和b分别指向了两个链表头A，B；

5) 假设La〉=Lb，使a向后移动La-Lb个结点；

6) 在循环体中，检验a是否等于b，如果相等则返回a；否则a，b后移一个结点；



6. 给定一个单向链表（可能是循环链表）的头指针，如何找出这个链表循环部分的第一个节点？

哪个公司考这么变态的题呀，不想招人就算了，这么找人开涮也太不厚道了。

1) 算法3检验是否有环，如果无环则返回，有环继续；

2) 在算法3停止的位置断开环；

3) 用算法5找出环的第一个结点；

4) 遍历到链表末尾，恢复环。

  

总结:

以上几道题有一个共同的特点，就是定义两个指针变量，并使其形成特定的位置关系，循环移动之后就能得到想要的结果，这就是这类题的固定模式了。也是本文的标题“两个变量”的由来。

1. 两个指针变量形成移动二倍关系，一个移动到尾部时，那么另一个就在中间；

2. 两个指针变量形成相距k的关系，一个移动到尾部时，那么就在倒数k的位置；

3. 两个指针变量形成快慢关系，如果轨迹是圆环，那么快的就能追上慢的；

4. 两个指针变量都移到可能的交叉点之后的对等位置（到交叉点距离相同），如果变成了同一个指针，那么就是相交的；

5. 两个指针变量找到第一个的对等位置（到交叉点距离相同），再平行移动，那么就能在交叉点相遇；

6. 3 + 5