链表题型解题技巧

链表解题模板：
1.双指针法（可以解决大约百分之60的题目）
两个关键点：
由于链表是同向的，因此双指针法的不同主要在下面两点
（1）双指针的起始距离
（2）双指针的移动速度
根据上述的一个或两个不同可以找到链表的中位数、链表的倒数第n个数等。
2.递归法（recursion）
递归法三个关键步骤：
（1）询问子问题的解；（注意此时将子问题想象成一个黑盒子，不用思考其内部结构，跳出来想）
（2）在当前递归层做满足题目要求的事情；例如反转链表时，需要将指针的指向进行变换。
（3）返回当前层的结果。
之所以采用递归法求解链表相关的问题是因为:单链表只能从头结点开始，依次访问下一个结点；这一点与数组不一样，数组可以从任意一个索引进行访问；因此对于链表如果能够从链表尾部开始访问就方便很多，递归法正是利用了这一特性，当询问子问题的解时，此时默认为子问题已解决，则此时链表好像是可以从尾端访问一样。

递归法代码模板：
ListNode * recursion(ListNode* head,其他参数)
{
//base case,也就是递归最简单的子问题
if(最简单子问题满足的条件)
{
…
return 链表头结点；
}
//递归操作
（1）寻求子问题解
ListNodelast = recursion(ListNode head.next,…);
(2) 实现满足题目要求的事情
…(例如断开连接，重新连接等)
（3）返回当前层的结果
return last;
}
后续将以若干个例子阐述对于不同链表问题如何套用代码模板。

最后

以上就是难过鸡翅为你收集整理的链表题型解题技巧的全部内容，希望文章能够帮你解决链表题型解题技巧所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。