【一】前言
2022经济寒冬之下，在年末之际来得更为惨烈，企鹅、宇宙等大厂相继爆出裁员消息后，某米，某站等也大批量裁员。不由得感叹，互联网的时代如今真的一去不复返了！作为互联网搬运工，码农们是最大的受害者，年底了短时间无法快速找到合适的下家，一个原因是迫于经济形势压力很多大厂都在收缩HC，另一个原因是大量的应届和被裁工程师都加入到找工作大军里面。这个形势下要找到下一份心仪的合适的令人向往的大厂offer，竞争就变得异常激烈了！唯有提升自己才是王道，面试中考算法已经变得非常普遍了，平时工作没有时间好好地练习算法，短时间内快速掌握算法技巧应对面试是重中之重。常用的算法有：动态规划、贪心算法、回溯算法、深度优先、广度优先、递归、双指针、快慢指针、迭代、哈希、二分等。
链表系列是算法题里面常见题型，通常涉及哈希、迭代、指针、递归的算法，下面介绍几个LeetCode上关于链表的题目。
【二】合并链表
LeetCode 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
【解法一】普通迭代：新建一个新的链表，用以存储合并链表的元素值，遍历并比较l1和l2两个链表元素值大小，小的那个放到新的合并链表末尾，直到遍历完两个链表后，最后判断两个链表是否都为空了，如果不为空则把剩余的元素添加到合并链表的末尾。
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } ListNode headerNode = new ListNode(-1); ListNode merge = headerNode; if(list1 != null && list2 != null){ if(list1.val <= list2.val){ merge.next = list1; list1 = list1.next; }else{ merge.next = list2; list2 = list2.next; } merge = merge.next; } //最后要判断一下list1和list2是否都为空，不为空则把剩余节点添加到merge末尾 merge.next = list1==null?list2:list1; return merge.next ; } }
【解法二】递归解法：递归的终止条件，如果l1或l2两个中的某个链表为空，则直接返回另外一个链表，递归条件，当l1的元素节点的值比l2小的时候，继续递归该方法，l1的next为左参数值，否则当l2的元素节点值比l1小的时候，继续递归该方法l2的next节点为方法的左参数值，继续递归该函数。
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1 == null){ return list2; } if(list2 == null){ return list1; } if((list1.val <= list2.val ){ ListNode pNode = mergeTwoLists(list1.next,list2); return pNode; }else{ ListNode pNode = mergeTwoLists(list2.next,list1); return pNode; } }
【三】相交链表
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
【解法一】哈希解法：新建一个HashSet<ListNode>的集合，先遍历listA链表，把元素存储进去到set集合里面，再遍历listB链表，在遍历B链表的时候，如果set集合里包含有相同的元素，则返回该节点结束遍历，否则遍历完未匹配则返回null。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } Set<ListNode> dataNode = HashSet<ListNode>(); ListNode temp = headA; while(temp != null ){ dataNode.add(temp); temp = temp.next; } temp = headB; while(temp != null ){ if(dataNode.contains(temp)){ return temp; } temp = temp.next; } return null; }
【解法二】双指针法：分别定义p1和p2两个指针指向headA和headB，同时移动p1和p2，当p1走到末尾节点时，next指向空，这时把p1指向p2的头结点，继续向前移动指针；当p2走到末尾节点时，next指向空，这时把p2指向p1的头节点，继续向前移动指针；当p1=p2时，这时就到了两个链表相交的地方，返回相交的节点即可。否则没有相交返回null。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode p1 = headA; ListNode p2 = headB; while(p1 != p2 ){ if(p1 == null){ p1 = headB; }else{ p1 = p1.next; } if(p2 == null){ p2 = headA; }else{ p2 = p2.next; } } return p1; } }
【四】反转链表
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
【解法一】递归法：链表反转操作符合递归的条件：大问题可以拆解为相同的无数个小问题，小问题相加累计结束就是大问题；递归终止条件，当链表为空或者链表只要一个元素时，直接返回该链表。定义一个用来返回的链表，并且以递归调用（节点的下个节点next）形式；递归的逻辑，用节点head为例需要反转把指针调转表示为head.next.next（原来指向下下个节点）仍然指回来指向自己head，这样指针就反转了；最后要把head的头结点也就是反转后的头结点的下个节点next置为null（防止出现环）。
class Solution { public ListNode reverseList(ListNode head) { //递归解法 //1.递归终止条件 if(head == null || head.next == null){ return head; } ListNode p = reverseList(head.next); head.next.next = head; head.next = null; return p; }
【解法二】指针法：新建一个prev链表用于存储返回结果得到链表，新建一个curr链表指向head链表用来遍历的链表，遍历链表curr当链表不为空时，把链表当前的下一个节点next保存下来，把当前节点的下一节点next指针指向prev ，把prev设置为当前节点curr（相当于开始移动指针），把当前节点curr设置为next节点。循环遍历链表直至结束，即把原链表反转了。
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev ; } }
【五】回文链表
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
【解法一】数组+双指针法：先用数组把链表的元素值存储起来，最后再用双指针头指针从前到后开始移动，尾指针从后往前开始移动，每次移动2个指针直至遍历完链表元素值都相等则判断是回文链表，否则不是回文链表。
class Solution { public boolean isPalindrome(ListNode head) { List<Integer> dataList = new ArrayList<Integer>(); while(head != null ){ dataList.add(head.val); head = head.next; } int p1 = 0; int p2 = dataList.size()-1; while(p1<p2){ //双指针不用循环，条件判断头尾指针相等时结束 if(!dataList.get(p1).equal(dataList.get(p2))){ return fasle; } p1++; p2--; } return true; }
【解法二】快慢指针法：先获取链表的前半部分，返回获得前半部分链表的最后一个元素，再反转后半部分链表（参数为前半部分链表的next节点），遍历反转后的后半部分链表，遍历完反转后的后半部分链表后，比较该反转后的后半部分链表元素与题干入参的链表head中的元素，都相等则判断是回文链表，否则不是。先获取链表的前半部分：快慢指针获取，快指针移动2个节点，慢指针移动1一个节点，当快指针到达末尾时，慢指针刚好走到链表的一半的位置。
反转后半部分链表：参考【三】
class Solution { public boolean isPalindrome(ListNode head) { if(head == null){ return true; } //获取到前半部分链表的元素(注意，这时链表指向前半部分最后一个节点) ListNode firstHalfNode = reverseHalf(head) ); //反转后半部分链表，从前半部分的最后一个节点得到next节点开始 ListNode reverseHalfNode = reverseNode(firstHalfNode.next) ); //遍历反转后的后半部分链表，遍历完所有反转的后半部分链表，所有元素都相等表示属于回文链表 ListNode temp = head; while(reverseHalfNode != null){ if(temp.val != reverseHalfNode.val){ return false; } reverseHalfNode = reverseHalfNode.next; temp = temp.next; } return true; } //1.通过快慢指针法获取前半部分的链表 public ListNode getFirstHalf(ListNode head){ ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } //2.反转前半部分的链表元素 public ListNode reverseNode((ListNode head){ ListNode prev = null; ListNode curr = head; while(curr != null){ ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }
【六】环形链表
141. 环形链表
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
【解法一】哈希法：
新建一个以ListNode为数据类型的Set集合，遍历链表并把链表的节点存储在Set集合里面，如果在遍历的过程中发现Set集合含有某个节点，在判断为环形链表。
public class Solution { public boolean hasCycle(ListNode head) { while(head == null || head.next == null){ return false; } Set<ListNode> dataNode = new HashSet<ListNode>(); ListNode temp = head; while(temp != null){ if(dataNode.contains(temp)){ return true; } dataNode.add(temp); temp = temp.next; } return false; } }
【解法二】快慢指针法：
也称为龟兔赛跑法，fast的指针在head.next处，slow的指针在head处，同时移动fast指针和slow指针，fast指针移动2个节点每次，slow移动1个节点每次，当fast指针和slow指针遍历完链表后，fast和slow也没有相等，则表示该链表不是环形链表（注意：起始时把fast置为head.next而不是head是假设在head之前两个节点开始移动，这样才能进入while循环）。
public class Solution { public boolean hasCycle(ListNode head) { while(head == null || head.next == null){ return false; } ListNode fast = head.next; ListNode slow = head; while(fast != slow){ if(fast == null || fast.next == null){ return false; } fast = fast.next.next; slow = slow.next; } return true; } }
快慢指针简化：
快慢指针同时在head位置处，while循环终止条件是当fast移动至链表末尾还没有发现快慢指针相碰则返回false
public class Solution { public boolean hasCycle(ListNode head) { while(head == null || head.next == null){ return false; } ListNode fast = head,slow = head; while(fast != null && fast.next != null){ if(fast == slow ){ return true; } fast = fast.next.next; slow = slow.next; } return false; } }
【七】总结
关于链表的常用解法，有：快慢指针法，递归法，哈希法，迭代法。拿到题目先分析题型场景适用于哪个算法，找到对应算法后再思考解题逻辑，从而一步一步写出对应的题解的代码来。
如果是求环相关的可以使用快慢指针法，如果是求反转链表可以使用递归和迭代，如果是求合并链表可以用迭代法（新建链表头-1开始），如果是求回文链表可以使用数组+双指针法，如果是求相交链表，可以用双指针和哈希法（分别遍历2个链表，有相同节点则为相交）。
