链表题目汇总

约定不等于承诺〃 2022-05-26 07:27 185阅读 0赞

## 单链表 ##

1.[单链表反转][Link 1]

2.[找出单链表的倒数第4个元素][4]

3.[找出单链表的中间元素][Link 2]

4.[删除无头单链表的一个节点][Link 3]

5.[两个不交叉的有序链表的合并][Link 4]

6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。

写程序把这个二级链表称一级单链表。

7.[单链表交换任意两个元素（不包括表头）][Link 5]

8.[判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？][Link 6]

9.[判断两个单链表是否相交][Link 7]

10.[两个单链表相交，计算相交点][Link 8]

11.[用链表模拟大整数加法运算][Link 9]

12.[单链表排序][Link 10]

13.[删除单链表中重复的元素][Link 11]

这些题目在面试中经常出现，所以在这个专题中总结一下，

我所使用的代码都是C/C++。

会写一些思路，这样就不必看代码了。

冰冻三尺，非一日之寒，让我们慢慢来练习吧。

链表的节点定义如下：

struct node
    {
    	char val;
    	node * next;
    };

用结构体定义，而不是用类。

从使用的方便来说，类要更好一些，

但是为了和其他关于链表的地方保持一致还是使用了结构体来定义。

节点元素为char型，是为了输出和调试方便。

注：这些题目都是前人总结的。

总结：

1，使用指针时，一定要检查指针是否为空；

2，要考虑特殊情况，如指针为空，空链表（只有表头结点），只有一个结点等；

3，插入，删除，交换等操作时都需要使用当前结点的前驱，需要同时记录下来；

4，单链表有无环以及交叉链表求相交结点的两个题目有很大的联系，

也是经常考的题目，有些题目可以转化成这类题目；

5，递归思想很重要，在链表的倒序输出，反转，模拟大数相交，

快速排序中都有用到，分治算法往往需要用递归来做；

6，快慢指针的思想很重要，常数时间删除结点的算法也很考察智力。

[Link 1]: http://blog.csdn.net/huangxy10/article/details/8011046
[4]: http://blog.csdn.net/huangxy10/article/details/8011150
[Link 2]: http://blog.csdn.net/huangxy10/article/details/8011186
[Link 3]: http://blog.csdn.net/huangxy10/article/details/8011191
[Link 4]: http://blog.csdn.net/huangxy10/article/details/8011275
[Link 5]: http://blog.csdn.net/huangxy10/article/details/8014009
[Link 6]: http://blog.csdn.net/huangxy10/article/details/8014148
[Link 7]: http://blog.csdn.net/huangxy10/article/details/8014233
[Link 8]: http://blog.csdn.net/huangxy10/article/details/8014276
[Link 9]: http://blog.csdn.net/huangxy10/article/details/8014434
[Link 10]: http://blog.csdn.net/huangxy10/article/details/8015079
[Link 11]: http://blog.csdn.net/huangxy10/article/details/8014602