leetcode链表题通解（打通任督二脉）

废话篇 我之前做链表题一直 很拉 很多时候 连leetcode上的简单题都不会
直到 前几天 我做笔试 遇到了 一道链表的题 竟然不会做 不会就查 重排链表
这一查 就学到了 一个 绝好的方法 ，打通了任督二脉 直接继承了我做数组题的修为

正文

个人总结 链表的题总共分为三种

第一种 用 list 集合 去存储节点

当节点存储以后， 不论如何去修改节点的后一位 节点也不会丢失
因为 节点位置已经被存储了 定位了 这个时候 你就可以 任意的拿取 list中的的结点了

用这种方法去做题 通常分为三步
第一步 获取节点 通常操作如下

    List<ListNode> list=new ArrayList<>();//做存储空间ListNode node=head;while (node!=null){//循环获取全部链表list.add(node);node=node.next;}

第二步 制作一个节点 将list’中的节点按照题目要求的方式连接到该节点后面（这里就运用到数组的知识）

该部分没有固定写法 看个人习惯

第三步 最重要的一步
将最后的 节点的下一步变为空
然后 返回你创造的最开始结点的下一步即可

例题1

简单难度的

class Solution {public ListNode reverseList(ListNode head) {//第一步 获取全部结点List<ListNode> list=new ArrayList<>();ListNode node=head;while (node!=null){list.add(node);node=node.next;}//第二步  根据题 去排列 node=new ListNode();//做头部ListNode node1=node;while(list.size()!=0){node.next=list.remove(list.size()-1);node=node.next;}//第三步 最后一位的下一位变空node.next=null;return node1.next;}
}

例题二

中等难度的

   class Solution {public void reorderList(ListNode head) {//第一步 获取全部结点List<ListNode> list=new ArrayList<>();ListNode node=head;while (node!=null){list.add(node);node=node.next;}//第二步  根据题 去排列 list.remove(0);ListNode node2=head;while ( list.size()!=0){node2.next=list.get(list.size()-1);list.remove(list.size()-1);node2=node2.next;if (list.size()!=0){node2.next=list.get(0);list.remove(0);node2=node2.next; }}//第三步 最后一位的下一位变空  本题是原位置修改所以无返回node2.next=null;}
}

例题三

困难难度的

class Solution {public ListNode reverseKGroup(ListNode head, int k) {//第一步 获取全部结点List<ListNode> list=new ArrayList<>();ListNode node=head;while (node!=null){list.add(node);node=node.next;}//第二步  根据题 去排列 ListNode abcd=new ListNode();node=abcd;while (list.size()>=k){for (int i = k-1; i >=0 ; i--) {abcd.next=list.remove(i);abcd=abcd.next;}   }while (list.size()>0){abcd.next=list.remove(0);abcd=abcd.next;}//第三步 最后一位的下一位变空abcd.next=null;return node.next;}
}

3道例题
难度 不同 但是做题方法相同

注 ：该方法虽然好用 但是 空间 浪费较大 该方法适合新手去 学习 练习 领悟

第二种 快慢双指针 法

这种方法通常 是用在那种 求共同的节点 或者说 循环节点的位置 的题

具体方法为

先定义 两起点
一个起点 按照 一步一步的走 ，一个起点 按照 两步两步的走。
走完后，都回到各自节点的开始
继续走 直到相遇的位置 就可以说明 是 循环链表
然后可以用该节点去找入环口 （例题二中有说明方法）

如果是两个不同的起点的 链表的共同结点 通常该节点就是入环口

注意 两步走的时候有可能会 报空指针 异常 需要 先 进行判断下一步是否为空的操作 然后看情况运行

例题一

public class Solution {public boolean hasCycle(ListNode head) {//第一步 定义两个节点ListNode ps = head;ListNode pf = head;//第二步  不断循环  本题意思是是找节点 如果有 就返回true 如果没有就返回false while (pf != null && pf.next != null) {ps = ps.next;pf = pf.next.next;if (ps == pf)return true;}return false;}
}

例题二

这个比第一道来说 多出了一个寻找入环点

参考leetcode的 官方题解

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode slow = head, fast = head;while (fast != null) {//外循环判断是否为循环链表slow = slow.next;if (fast.next != null) {fast = fast.next.next;} else {return null;}if (fast == slow) {//进入内循环 查找进入节点ListNode ptr = head;while (ptr != slow) {ptr = ptr.next;slow = slow.next;}return ptr;}}return null;}
}

例题三

困难题没找到 再难基本就是数据结构的知识了

方法三

这第三种方法 通常是需要领悟的
很多的题 有时空复杂度的限制 这样就不能用第一种的方法了
但是 当第一种方法用多的时候 很多东西自己就悟到了
比如 什么时候开新链表
什么时候下一步变为空 等等

这里 就 提供几个例题 供参考吧

例题一

class Solution {public static ListNode swapPairs(ListNode head) {ListNode A=new ListNode();//做头ListNode B=A;//备份头部A.next=head;while (A.next!=null&&A.next.next!=null){//不断循环 接头部ListNode C=A.next;ListNode D=A.next.next;A.next=D;C.next=D.next;D.next=C;A=C;}return B.next;//返回头部下一个}
}

例题二

这道题是我去年做的 运用了 锁的思想 不断的获取最小的 应该算是去年稀里糊涂做出来的 有点潦草 但是思想可以看看

class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode new1=new ListNode();ListNode new2=new1;boolean A=true;while (A){A=false;int indxe = -1;for (int i = 0; i <lists.length ; i++) {//判断说有链表中头最小的if (lists[i]!=null){A=true;if(indxe==-1){indxe=i;}else {if (lists[i].val<lists[indxe].val){indxe=i;}}}}if (A){//添加最小的  并删除链表池中的该元素 new2.next=lists[indxe];lists[indxe]=lists[indxe].next;new2=new2.next;}}return new1.next;}
}

呜呜呜 就这 了 如果对你有用 记得点赞 关注加收藏哦 【ღ( ´･ᴗ･` )比心】