【声明】：由于笔者水平有限，在今后的博文中难免会出现错误和不准之处，本人也非常渴望知道这些错误，恳请读者批评斧正，期待您的留言评论。
文章目录
目录
唠叨一下：做数据结构题目时不论难易，一定要画图理解，包括后期发布的递归也是这样，千万千万不能懒惰哦！
4.链表分割：所有小于x的节点排在大于等于x的节点之前（字节跳动笔试题）
唠叨一下：做数据结构题目时不论难易，一定要画图理解，包括后期发布的递归也是这样，千万千万不能懒惰哦！
一、十大链表必刷题有哪些？
1、反转链表
2、找到链表的中间节点
3、找到链表中倒数第k个节点
4、链表分割，所有小于某个数的节点都放在大于或者等于那个数的节点之前
5、删除已经排好序的链表中重复的节点
6、链表的回文结构
7、环形链表I:判断链表是否有环
8、环形链表II:找入口节点
9、相交链表：找到两个链表相交的起始节点
10、合并两个已排好序的链表
11、删除所有出现关键字为key的节点(嘻嘻，你不会真的天真的以为只有十题吧..)
二、算法分析及代码示例
//无头单向非循环链表 class Node { //实例成员没有初始化，默认值为对应的0值，引用类型默认为null，简单类型默认为0 public int data;//数值域---0 public Node next;//下一个节点的引用---null public Node(int data) { this.data = data; this.next = null; } }
1.反转链表（剑指offer）
思路：有两种方法：一是直接翻方向，二是利用头插法，因为该题比较简单，直接看代码示例就能理解，不过在这里，笔者要再强调一遍的是，不管多简单的题目，一定要画图理解，千万不能眼高手低！！！
代码如下（示例）：
//1、反转链表 //方法一：直接翻方向（最好掌握这个方法，因为在后面的“回文结构”中也用到了这个方法） public Node reverseList(Node head) { Node prev = null;//需要反转的节点的前驱 Node cur = head;//需要反转的节点 Node newHead = null;//反转后的单链表的头 //遍历链表 while(cur != null) { Node curNext = cur.next;//需要反转的节点的后继 if(curNext == null) { newHead = cur; } cur.next = prev; prev = cur; cur = curNext; } return newHead; } //方法二：头插法（取原链表的节点，头插到新链表）（相对于直接翻方向容易理解一些） public Node reverseList1(Node head) { Node cur = head;//进行头插的节点 Node newHead = null; while(cur != null) { Node curNext = cur.next;//进行头插的节点的后继 cur.next = newHead; newHead = cur; cur = curNext; } return newHead; }
2.找到链表的中间节点
NB（注意）：如果有两个中间节点，则返回第二个
思路：利用快慢指针fast和slow，两个都从头开始走，fast一次走两步，slow一次走一步，当fast == null || fast.next == null 时，slow就是中间结点
代码如下（示例）：
public Node middleNode(Node head) { Node slow = head; Node fast = head; //只要fast或者fast.next有一个为空，那么肯定走到尾了，注意别忘记加上fast.next!=null //注意不能写成fast.next != null && fast != null这样，因为fast走两步后可能为空了，再执行 //循环fast.next可能会导致空指针异常 while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }
3.找出单链表中倒数第k个节点（剑指offer）
思路：还是利用快慢指针fast和slow，fast先走k-1步，然后fast和slow每个同时走一步，当fast.next==null时，slow就是所求
public Node FindKthToTail(Node head, int k) { //单链表不能为空 if(head == null) { return null; } //先判断k的合法性 //此处为了只需一次遍历单链表就能解决问题，同时也为了提高时间效率，没有加上k > size()这个 //条件，所以后面要注意空指针异常(第一个while循环做了处理)，size()实际上是我写的求单链表 //长度的方法，在此你只要将k > size()理解成"k > 单链表的长度"即可 if(k <= 0) { System.out.println("k不合法！"); return null; } Node slow = head; Node fast = head; //不能让它一直往后面走，可能会导致空指针异常 while(k - 1 > 0) { //设置fast.next != null这个条件就是防止k大于单链表的长度 if(fast.next != null) { fast = fast.next; k--; }else { System.out.println("没有这个节点！"); return null; } } while(fast.next != null) { fast = fast.next; slow = slow.next; } return slow; }
4.链表分割：所有小于x的节点排在大于等于x的节点之前（字节跳动笔试题）
NB：链表分割以后需要保证原来的数据顺序不变-----所以采用“尾插法”
思路：
- 设置两个线段的开始还有结束，分别是bs,be,as,ae
- 定义一个cur,遍历原来的单链表
- 如果cur.data < x,就放到第一个线段，反之，放到第二个线段，注意，为了保证分割链表以后原来的数据顺序不变，此处采用“尾插法”，需要注意的是，一定要判断是不是第一次插入数据，因为第一次和其他次插入数据所执行的操作是不一样的
- cur == null时，原来的单链表就遍历完了
public Node partition(Node head, int x) { Node bs = null; Node be = null; Node as = null; Node ae = null; Node cur = head; while (cur != null) { if (cur.data < x) { //第一次插入(bs为空时) if (bs == null) { bs = cur; be = cur; } else { be.next = cur; be = be.next; } } else { //第一次插入（as为空时） if (as == null) { as = cur; ae = cur; } else { ae.next = cur; ae = ae.next; } } cur = cur.next; } //1、判断bs是否为空，如果bs == null,返回as if (bs == null) { return as; } //2、如果bs不为空，需要进行拼接 be.next = as; //3、如果ae不为空，ae.next需要置为空 if (ae != null) { ae.next = null; } return bs; }
5.删除已经排好序的链表中重复的节点（字节跳动笔试题）
注意：1、已经排好序的链表就意味着重复的节点集中在一起，读题时就要联想到这一点
2、该题是将重复的节点全部删除干净
思路：定义一个虚拟节点来解决问题（也就是将没有重复出现的节点放到一个新的链表当中）
public Node deleteDuplication(Node head) { Node cur = head; Node newHead = new Node(-1);//定义的虚拟节点 Node tmp = newHead; while(cur != null) { //一定要加上cur.next != null这个条件，防止一直朝后走导致空指针异常(因为后面要判断 //cur.data == cur.next.data,涉及cur.next，所以要多想一下) if(cur.next != null && cur.data == cur.next.data) { while(cur.next != null && cur.data == cur.next.data) { cur = cur.next; } cur = cur.next;//多走一步(因为要把重复的节点全部删除掉) }else { tmp.next = cur; tmp = tmp.next; cur = cur.next; } } tmp.next = null;//最后一定不要忘记了将尾结点的next置为空 return newHead.next; }
6.链表的回文结构（腾讯笔试题）
注意：用到了前面的反转链表和找链表的中间节点这两个方法的算法思想
思路：1、找到中间节点
2、翻转链表后半部分的节点
3、先从奇数个节点入手，最后再考虑偶数个节点的情况
public boolean chkPalindrome(Node head) { //单链表为空，肯定不是回文结构 if(this == null) { return false; } //只有头结点自己，肯定是回文结构 if(head.next == null) { return true; } //1、找到单链表的中间节点 Node fast = head; Node slow = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //2、开始反转单链表的后半部分 slow肯定在中间位置 Node cur = slow.next; while(cur != null) { Node curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } //slow是最后的节点了 //3、开始一个从头走，一个从尾走 while(slow != head) { if(slow.data != head.data) { return false; } //判断偶数的情况(一定要注意的是不能比较的是元素大小！！！) if(head.next == slow) { return true; } slow = slow.next; head = head.next; } return true; }
7.环形链表I：判断链表是否有环（百度笔试题）
思路：本题很简单，利用快慢指针做即可
public boolean hasCycle(Node head) { Node fast = head; Node slow = head; //如果有环，必然不会存在null while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { return true; } } return false; }
8.环形链表II：找入口节点（腾讯笔试题）
思路：1、设环的长度为C，相遇时fast走了N圈，从头到入口点的距离为X，入口点到相遇点为Y；
2、如果有环，fast和slow相遇的时候，fast走的路程是slow的两倍，2 * (X + Y) = X + NC + Y----->X + Y = NC----->X = NC - Y
3、NC是一个定值，当N == 1时，相遇点到入口点的距离就是X，此时使用两个引用，一个 从头开始走，一个从相遇点开始走，当二者相遇的时候就是入口点
public Node detectCycle(Node head) { Node fast = head; Node slow = head; //如果有环，必然不会存在null while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { break; } } if(fast == null || fast.next == null) { return null; } //相遇后，即有环，此时使用两个引用，一个从头开始走，一个从相遇点（此时的slow和fast就在相 //遇点）开始走，当二者相遇的时候就是入口点 slow = head; while(slow != fast) { slow = slow.next; fast = fast.next; } return slow; }
9.相交链表（剑指offer）
思路：1、求两条单链表的长度
2、计算两条单链表的差值
3、让长的链表先走差值步，后面详细步骤见代码块即可求出两链表第一次相交节点
public Node getIntersectionNode(Node headA, Node headB) { //1、求长度，走差值步 int lenA = 0; int lenB = 0; Node pl = headA; Node ps = headB; while(pl != null) { lenA++; pl = pl.next; } while(ps != null) { lenB++; ps = ps.next; } //注意此时pl，ps位置不再是头了，需要人为设置 pl = headA; ps = headB; //len要放到这个位置计算，最基本的都忘记了！！！ int len = lenA - lenB; //保证pl里面放的是长链表，ps里面放的是短链表 if(len < 0) { pl = headB; ps = headA; len = lenB - lenA; } //长的链表走差步值 for(int i = 0; i < len; i++) { pl = pl.next; } //2、ps和pl一定在同一个起跑线上 //设置ps != pl这个条件就是为了相交的时候停下来 //别忘了pl != null && ps !=null 这个条件,其实也可以省去，因为两链表剩下的节点一样长！ while(ps != pl && pl != null && ps != null) { ps = ps.next; pl = pl.next; } //二者相等也可能是两条链表都为空了 if(pl == ps && pl != null) { return pl; } return null; }
10.合并两个有序的链表（剑指offer）
思路：利用虚拟节点即可
public Node mergeTwoLists(Node headA, Node headB) { //开辟一个虚拟节点 Node newHead = new Node(-1); Node tmp = newHead; while(headA != null && headB != null) { if(headA.data < headB.data) { tmp.next = headA; headA = headA.next; tmp = tmp.next; }else { tmp.next = headB; headB = headB.next; tmp = tmp.next; } } if(headA != null) { tmp.next = headA; } if(headB != null) { tmp.next = headB; } return newHead.next; }
11.删除所有关键字为key的节点（剑指offer）
思路：本题比较简单，但是最后别忘记了要回过头来判断第一个节点
public void removeAllKey(Node head, int key) { //单链表为空时 if(head == null) { return; } //需要注意的是始终要保证prev是cur的前驱 Node prev = head; Node cur = head.next;//代表要删除的节点 while(cur != null) { if(cur.data == key) { prev.next = cur.next; cur = cur.next; }else { prev = cur; cur = cur.next; } } //最后再判断首节点 if(head.data == key) { head = head.next; } }
总结
与其说它是十大链表必刷题，不如把“十大”改成“十类”，因为LeetCode和牛客网等刷题网站上面至少80%的题目都是这十类题目本身，或是其变形形式，中心算法思想是一致的，稍稍改动即可，不过若要会做变形形式，首先需要将这些最基本的原题烂熟于心，数据结构的重要性不用说大家都明白，链表在数据结构中也是举足轻重的。
可能我们在听老师讲课的时候，或者就拿上面的代码举例吧，我们听或者看的时候，能听懂也能看懂，但是到自己实现起来就不是那么一回事了，笔者本人也是这样，究其原因呢，还是题目刷少了，代码量跟不上！所以平时要多练习，笔者自己呢，也是刚刚开始刷LeetCode没多长时间，希望与大家共同进步。
此处需要敲黑板——若要真正掌握上面的题目，我们最起码要练习五遍以上，而且每一遍都要画图理解，包括之后即将发布的递归也是这样，我们处在一个非常美好的时代，时不我待，万万不能懒惰呀铁子们，我自己也是！
还有还有，感谢铁子们能看到最后，蟹蟹啦！
