leetcode题型分析《链表》

1 单向链表

增加dummy节点，减少代码复杂程度，不用担心头节点为空的情况。

剑指offer II 21 删除倒数第N个节点

思路：定有两个指针，让指针一先走N步，然后两个指针一起前进，当指针一到达链表尾部时，指针二位于倒数第N个节点。

剑指offer II 22 链表中环的入口节点

思路：定义快慢指针，快指针一次走两步，慢指针一次一步，当快慢指针相遇时，将快指针重新指向头，然后一次一步，当快慢指针再次相遇时，即为环的入口点。

剑指offer II 23 两个链表的第1个重合节点

思路1：定义p1,p2指针分别指向链表list1和list2，当p1或者p2遍历到链表尾时，又重新从list2或者list1头开始，当再次相遇即为重合节点。

思路2：定义两个栈，分别将list1和list2加入栈中，然后比较，当两个栈节点相等节点即为重合节点。

剑指offer II 24 反转链表

思路：用三个指针分别指向当前节点，前一个节点，和下一个节点。

 有于当前节点j会与下一个节点k之间出现断裂，所以定义一个next节点将cur.next保存起来，为改变其指向让cur.next = prev;然后递推prev  = cur; cur = next;

 剑指offer II 25 链表中的数字相加

思路：想把两个链表反转，再把反转之后的链表逐个相加，最后把表示和得链表反转。

2 双向链表和循环链表

剑指offer 28 展平多级双向链表

思路：链表里面嵌套子链表，子链表又继续嵌套子链表适合用递归解决该问题。定义递归函数getTail()或者链表尾，然后将其插入上一级链表。

 

剑指offer 29 排序的循环链表

思路：试图找到两个相邻的节点，如果待插入节点位于相邻节点之间插入，如果没有则表明待插入节点可能是最大最小值插入原本最大最小值之间。