JavaOj & 链表十连问
Java数据结构 & LinkedList & 链表_s:103的博客-CSDN博客
紧接上文，我们开始投入链表的oj题中吧~
最后我补充两个个知识点
LinkedList链表的反向遍历~
ArrayList与LinkedList区别
链表归并排序~【涉及排序原理】
1. 删除链表中等于给定值 val 的所有节点
203. 移除链表元素 - 力扣（Leetcode）
1.1 代码实现~
这个模式在数据结构的题目中，尤为常见，一定要重点熟悉~
这个类就是现成的节点类~
class Solution { public ListNode removeElements(ListNode head, int key) { if(head == null) { return head; } ListNode prev = head; ListNode cur = head.next; while(cur != null) { if(cur.val == key) { prev.next = cur.next; }else { prev = cur; }cur = cur.next; } if(head.val == key) { head = head.next; } return head; } }
1.2 深度讲解 + 动图分析
这道题就是我们的removeAllKey方法呀~
再讲一次~
删除所有同键值节点~
这个稍微复杂，思想仍然是（跳跃式忽视节点的方法）【即prev的后驱指向cur的后驱】
用到了一个前后指针的算法
prev一开始处于head的位置，cur在head.next的位置
遍历链表，结束条件是cur为null
正常情况下，即删除节点之前，prev和cur都是同步走的
但cur遇到要删除的节点的时候，要让cur去找下一个非此键值的节点（如果还是该键值，这个节点将不会被后续操作删除）或者null，cur每次遇到键值匹配的节点，size–
cur每次找到key，prev的后驱指向cur的后驱 ===》实现删除连续节点
cur一旦找不到key，prev就会继承cur的位置
最不应该忘记的是这个：
头节点留到最后再判断，如果一开始将头结点删了，那么后续仍然有头结点无法被判断，反反复复无法解决问题~，这样还不如先判断后面的节点，最后再判断头节点
如果头节点该删，head = head.next~
动图演示：
2.反转单链表
206. 反转链表 - 力扣（Leetcode）
2.1 代码实现
see it again~ class Solution { public ListNode reverseList(ListNode head) { if(head == null) { return null; } ListNode cur = head.next; head.next = null; while(cur != null) { ListNode curNext = cur.next; cur.next = head; head = cur; cur = curNext; } return head; } }
2.2 深度解析 + 动图分析
不知道你有没有联想到可以用头插法~
*你可能在链表学习中，在测试的时候会发现，连续头插的结果是逆序的，那么我们就可以借助这一现象，逆序链表，借助探路指针还有“**传送指针”*进行操作，且听我细细道来~
head 为 null，不用逆序，直接返回null
cur探路指针去遍历，curNext去记录cur的后驱，防止回收
将cur直接头插链表~
通过 “传送指针curNext” 前往原来的位置的后驱~
直到cur被传送到null，退出循环~
return head;
动图解析：
3. 链表的中间结点
876. 链表的中间结点 - 力扣（Leetcode）
3.1 代码实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast .next != null) { fast = fast.next.next; slow = slow.next; } return slow; } }
3.2 深度解析 + 动图分析
这里有一个很重要的思想
“快慢指针” --> 在Java中是引用
两个探路指针去探路，但是有一个指针速度是另一个的一倍，这就是快指针
那么快指针到达null的时候，慢指针就处于中间位置了~
但是要区分这个链表是偶数节点数还是奇数节点数~
我们可以通过节点数确定该节点的下标，但是我要求在只遍历一次的情况下去解决问题~
奇数：正中间节点~
偶数：正中间右节点~
很巧的是，题目要求的就是这个~
动图解析：
3.2.1 奇数：
3.2.2 偶数：
4. 链表中倒数第k个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
4.1 代码实现
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head == null) { return null; } ListNode fast = head; ListNode slow = head; for(int i = 0; i < k; i++) { fast = fast.next; if(fast == null && i < k - 1) { return null; } } while(fast != null) { fast = fast.next; slow = slow.next; } return slow; } }
4.2 深度解析 + 动图分析
通过第三题，我们这道题不难联想到，也可以用“快慢指针”
但是 “快慢指针” 一定要速度不相同吗？
显然不是必要的~
这里的快慢指针，有一个指针快人一步~
也就是说，除了速度快，还可以 “笨鸟先飞”~
我们学习也是要这样，虽然可能学得不快，但是可以先学~
我们当然也可以遍历两次表去解决这个问题，但是我要求只遍历一次~
那么我们就可以让fast的快指针，先走k步，然后再与slow一起走，那么fast走完的时候，slow的位置，就是倒数第k个~
因为fast与slow差距k，最终就是slow与null差距k~
结合牛客给的测试用例，有可能k很大，或者head为null~
我们要处理这些细节~
动图分析：
5.合并有序链表
21. 合并两个有序链表 - 力扣（Leetcode）
5.1 代码实现
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head = new ListNode(); ListNode cur = head; while(list1 != null && list2 != null) { if(list1.val <= list2.val) { cur.next = list1; list1 = list1.next; }else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if(list1 != null) { cur.next = list1; }else { cur.next = list2; } head = head.next; return head; } }
5.2 深度解析 + 动图分析
这时候我们就需要这个特殊的链表：带头链表
这头指针又称之为：“哨兵”
而根据它的用途，我更喜欢称之为：“外来异物”
外界异物侵入珍珠蚌内后，在保护机制下，珍珠蚌会分泌一种珍珠质，将异物层层包裹，最终形成了珍珠。
那么这个头，不是有效节点，但是可以帮助我们累积构造形成链表~
list1.val <= list2.val 那么就连接list1，list1往后走
反之，连接list2，list2往后走
无论连接谁，cur保持处于待构造表的尾部
动图解析：
6. 链表分割
链表分割_牛客题霸_牛客网 (nowcoder.com)
6.1 代码实现
public class Partition { public ListNode partition(ListNode pHead, int x) { if (pHead == null) { return null; } ListNode fast = pHead.next; ListNode prev = pHead; ListNode slow = null; ListNode cur = null; while (fast != null) { if (fast.val < x) { if (slow == null) { slow = fast; cur = slow; } else { cur.next = fast; cur = cur.next; } } else { prev.next = fast; prev = fast; } fast = fast.next; } prev.next = null; if (pHead.val < x) { ListNode tmp = pHead; pHead = pHead.next; tmp.next = slow; slow = tmp; } if (slow == null) { slow = pHead; } else { cur.next = pHead; } return slow; } }
6.2 深度解析 + 动图分析
这个问题会比较难，因为涉及多个中介节点
要求以给定的一个值为标准，小于该值的放在左边，大于该值放在右边，等于的话在哪边都无所谓~
并且要求，左右两条子链表是按照原来的顺序排的~
写一次不用 “外来异物” 的方法~
重要思想：
类似于单链表删除操作~
头节点不应该在最开始的时候进行判断，而是留到最后判断
fast做为最初的探路指针，它完整遍历原链表~
slow的存在是“较小数节点”的链表~
如果fast此时键值小于x
如果fast此时键值不小于x
处理原链表的头节点
连接两条链表~
6.2.1 头节点为较小节点图示：
6.2.2 头结点不为较小节点图示：
7. 回文链表
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
7.1 代码实现
public class PalindromeList { public boolean chkPalindrome(ListNode A) { ListNode fast = A; ListNode slow = A; if (fast == null) { return false; } while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //逆序后面的表 ListNode cur = slow.next; slow.next = null; while (cur != null) { ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } while (slow != null) { if (A.val != slow.val) { return false; } A = A.next; slow = slow.next; } return true; } }
7.2 深度解析 + 动图分析
回文，我们可以分别判断首与尾，首与尾，首与尾，就像顺序表那样~
但是这种算法的时间复杂度为O(N2)
我们可以逆序一整个链表，判断是否与原链表一样
我们可以只逆序一半，判断前半段与后半段是否相同
法2， 显然是最合适的~
这道题是中间节点，与逆序链表的结合题~
找到中间节点，用头插逆序的方法将后半段进行逆序
判断是否回文~
对于奇数偶数节点的链表，用刚才的方法有如上两种不同形式~
相交链表~
只要slow指针能达到null，则说明true~
只要不相等，直接返回false~
7.2.1 奇数节点链表后半段逆序 + 判断回文动图解释：
逆序后半段：
判断回文：
7.2.2 偶数节点链表后半段逆序 + 判断回文动图解释：
逆序后半段：
判断回文：
