力扣链表刷题总结（简单）
链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
对于链表相关的题通常可以通过迭代、转换为数组、单指针、快慢指针等方法去做。通常为了节省时间或空间复杂度，会优先考虑快慢指针进行解题，置于其他时候具体问题需要具体分析。
关于链表的一些小技巧：
- 当需要产生一个新链表时，不妨设置含有虚拟节点的链表来存储新链表，可避免出现空指针异常
- 当需要删除某个节点的时，不妨定位到待删除节点的上一个节点，next 指针，使其指向待删除节点的下一个节点，即可完成删除操作
- 当需要找到第K个节点时，不妨考虑快慢指针，快指针走K步，慢指针走N-k步，当快指针为空时，慢指针的位置即为我们所求
- 当需要寻找某个位置时，不妨快慢指针多走几遍，相当于第一遍确定位置，第二遍寻值
注：对于其他问题，要具体问题具体分析，不是所有链表问题都适合采用以上技巧。刷算法题时，要多动脑子，不能形成思维定式，从题目中，一点点抽取关键问题。
吾日三省吾身：
- 付出不亚于任何人的努力
- 自立，自省，自爱，自强
- 谦虚低调，不卑不亢，常怀感恩之心
以下列举综合性较强的题解：
//合并两个升序链表 /** *思路：链表相关的问题多可用快慢指针的解法，设置两个指针分别指向两个链表，依次比较大小 *本题亮点：当产生一个新链表时，就创建一个dummy【虚拟头结点】，可避免出现空指针异常。 */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //首先建立一个新的链表，用于存储合并后的链表 ListNode dummy = new ListNode(-1); //此处空间置为-1就是为了占位 ListNode p = dummy; //将list两个链表分别存储在p1,p2中 ListNode p1 = list1,p2 = list2; //当两个链表均不为0时，方可以进行排序 while(p1 != null && p2 != null){ if(p1.val> p2.val){ p.next = p2; p2 = p2.next; }else{ p.next = p1; p1 = p1.next; } p = p.next; } //当两个链表分别为空时，则直接返回另一个链表即可 if(p1 == null){ p.next = p2; } if(p2==null){ p.next = p1; } return dummy.next; } }
//删除链表的第N个节点 /** *思路：因为删除后会产生一个新链表，所以直接定义含一个虚拟节点的新链表。 * 要删除第N个节点，只需要让（N-1）的下一个指针指向下一个地址即可 * 因为定义了虚拟节点，所以此处为n.next = n.next.next; * 亮点：本题需要先找到倒数第N个节点。 再使用 n.next = n.next.next; */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //定义虚拟节点链表 ListNode dummy = new ListNode(-1); dummy.next = head; //删除倒数第N个，要先找到倒数第N-1个 ListNode x = Findfrom(dummy,n+1); x.next = x.next.next; return dummy.next; } //此处参考找链表中倒数第N个节点 //先去找第N个节点 public ListNode Findfrom(ListNode head,int k){ //先定义一个指针 ListNode p1 =head; //先遍历一次链表，找出N的位置 for(int i= 0 ; i < k; i++){ p1 = p1.next; } //再定义一个指针，此时p1 和 p2正好相差了N-K 步 ListNode p2 = head; //当p1为空，即指向链表的末尾是，p2的位置就是所需节点的位置 while(p1 != null){ p2 = p2.next; p1 = p1.next; } return p2; } }
//环形链表 /** * 思路：判断链表中是否含环，通常采用的是快慢指针的做法。 * 重点：先判定链表为空否，再判断快慢指针相等否 */ public class Solution { public boolean hasCycle(ListNode head) { //首先定义快慢指针 ListNode fast = head,slow =head; //判断给定链表是否为空链表，若为空，直接返回false if (head == null || head.next == null){ return false; } //若链表不为空，则判断快指针是否为空 while(fast != null && fast.next != null){ //不为空，则慢指针走一步，快指针走两步 slow = slow.next; fast = fast.next.next; //当二者相等时，则代表存在环路 if(slow == fast){ return true; } } return false; } }
//相交链表 /** * 思路：根据题目可以得出如果两个链表相交，那么相交点之后的长度是相同的 * 同样建立两个指针，分别指向两个链表，并且从头结点位置开始，消除两个链表的长度差 即可 * 让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //如果链表为空则无相交节点 if (headA == null || headB == null) return null; //建立两个指向链表头指针的节点 ListNode pA = headA, pB = headB; //等指针A.B不相等时，则证明无相交节点，继续遍历 while (pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }
