1. 删除链表中等于给定值 val 的所有节点。

删除某一个节点的原理就是不再有引用指向该节点，Java虚拟机会自动回收
如下链表：

假设给定值为3其结果为：

参考代码：

 //删除所有值为key的节点public void removeAllKey(int val){if(this.head == null){//若没有节点，直接返回return;}ListNode prev = this.head;ListNode cur = this.head.next;while(cur!=null){//节点不为空，进入循环if(cur.val == val){//找到一个与指定值相同的节点，删除prev.next = cur.next;cur = cur.next;//删除后向后移动一位}else{//与指定值不同，向后移动一位prev = cur;cur = cur.next;}}//最后判断头节点是否为该值if(this.head.val == val){this.head = this.head.next;}}

2. 反转一个单链表。

反转指的是反转节点，不是将节点的值反转
反转前：

反转后：

注意：单链表尾节点的next域为null

参考代码：

//反转一个单链表public ListNode reverseList(){//若没有节点或只有一个节点，直接返回if(head == null||head.next == null){return head;}ListNode cur = head;ListNode newHead = null;while(cur!=null){ListNode curNext = cur.next;//保留curNext,以便向后移动cur.next = newHead;//把本节点的next域置为newHeadnewHead = cur;//newHead节点向后移一位cur = curNext;//cur向后移一位}return newHead;}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

采用快慢指针法，慢指针每走一步，快指针走两步。当快指针走到末尾，慢指针也就走到了中间节点

开始时快指针和慢指针都在头节点

最后的位置

参考代码：

//给定一个带头节点的非空单链表，返回链表的中间节点public ListNode middleNode(){if(head == null) return head;ListNode fast = head;//快指针ListNode slow = head;//慢指针while(fast!=null && fast.next!=null){fast = fast.next.next;//走两步slow = slow.next;//走一步}return slow;//返回慢指针}

4. 输入一个链表，输出该链表中倒数第k个结点。

采用快慢指针法，快指针先走k-1步，然后快指针和慢指针同步向前走，直到快指针走到末尾

如下链表假设k为2，则其快慢指针的起始位置为：

其最后的结果为：

参考代码：

//输入一个链表，输出该链表中倒数第k个节点//先让快指针走k-1步，再让快指针和慢指针一起同步走public ListNode findKthToTail(int k){if(head == null) return null;//空节点if(k<0){//坐标不合法return null;}ListNode fast = head;ListNode slow = head;while(k-1 != 0){//处理k可能大于链表长度的情况if(fast.next != null){fast = fast.next;k--;}else{return null;}}while(fast.next != null){//快慢指针同步走fast = fast.next;slow = slow.next;}return slow;}

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

如下两个有序链表：

其拼接完成以后为：

参考代码：

    //将两个有序链表合并为一个新的有序链表并返回public ListNode mergeTowList(ListNode headA,ListNode headB){if(headA == null) return headB;if(headB == null) return headA;if(headA == null && headB == null) return null;ListNode newHead = new ListNode(-1);//申请一个头节点,傀儡节点ListNode tmp = newHead;//移动tmp，保留newHead位置while(headA != null && headB != null){//谁小先连接谁，直到其中一个达到尾结点if(headA.val<headB.val){//链接headAtmp.next = headA;headA = headA.next;}else{tmp.next = headB;//链接headBheadB = headB.next;}tmp = tmp.next;//连接后再向后移一位}if(headA == null){//headA先到尾结点tmp.next = headB;}if(headB == null){//headB先到尾结点tmp.next = headA;}return newHead.next;//返回傀儡结点的下一个结点}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 ，且保证顺序不变。

假定有如下链表：

如果给定值x为6

分别创建两个链表，前一个均小于x，后一个均大于x。为保证顺序不变应采用尾插法

参考代码：

//已给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前public ListNode partition(int x){ListNode cur = this.head;//用来遍历指定链表ListNode bs = null;//前一个链表的起始ListNode be = null;//前一个链表的末尾ListNode as = null;//后一个链表的起始ListNode ae = null;//后一个链表的末尾while(cur != null) {//使用尾插法来保证顺序不变if (cur.val < x) {if (bs == null) { //第一部分第一次插入bs = cur;be = cur;} else {//多次插入的连接be.next = cur;be = be.next;}} else {if (as == null) {//第二部分第一次插入as = cur;ae = cur;} else {//多次插入的连接ae.next = cur;ae = ae.next;}}cur = cur.next;//指定链表的遍历位置向后移一位}if(bs == null){//如果所有值都大于xreturn as;}//bs!=nullbe.next = as;//be不为空，该结点一定有数据，将其与后一个链表连接起来if(as != null){//若as不为空，将链表的尾节点的next域置为空ae.next = null;}return bs;}

7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

假设给定如下链表：

其删除完重复结点以后为：

参考代码：

    //删除一个有序链表中的重复结点，重复的结点不保留，返回链表头指针public ListNode deleteDuplication(){ListNode newHead = new ListNode(-1);//申请一个傀儡结点ListNode tmp = newHead;//移动tmp保证傀儡结点位置不动ListNode cur = this.head;while(cur != null){//cur.next!=null; 判断是不是只有一个节点 或者 是不是尾巴节点if(cur.next != null && cur.val == cur.next.val){//cur再走的过程中，有可能剩下的都是相同的while(cur.next != null && cur.val == cur.next.val){cur = cur.next;}cur = cur.next;//循环不满足，向后走一步}else{//尾插法tmp.next = cur;tmp = tmp.next;cur = cur.next;}}tmp.next = null;//手动设置，防止最后一个结点是重复的return newHead.next;}

8.判断链表是否回文结构

回文结构示例：

方法：

1. 首先通过快慢指针法找到链表的中间节点
   

2. 从中间节点开始对链表进行反转
   

3. head和slow两个指针分别从头和尾向中间匹配，直到两个指针对撞，一旦遇到不一致直接返回false，否则返回true
   
   注意：区分奇数和偶数的情况，偶数匹配时多比较一步

参考代码：

    //检查链表的回文结构，例如：12321public boolean chkPalindrome() {if (this.head == null) {//一个结点也没有return true;}if (this.head.next == null) {//只有一个结点return true;}//1找中间节点ListNode slow = this.head;ListNode fast = this.head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//slow 指向的节点就是中间节点//2,进行翻转ListNode cur = slow.next;while (cur != null) {ListNode curNext = cur.next;//保留cur.nextcur.next = slow;slow = cur;cur = curNext;}//反转完毕 slow指的地方就是最后一个节点while (slow != head) {if (slow.val != head.val) {return false;}if (head.next == slow) {//偶数情况return true;}head = head.next;slow = slow.next;}return true;}

9.输入两个链表，找出它们第一个公共节点

相交的链表链表具有Y型和X型

如下一个具有公共节点的链表：

方法：

1. 首先分别得到两个链表的长度，计算其差值x
2. 让长的链表先走x步，然后让两个链表边匹配值边走，直到末尾

参考代码：

 //输入两个链表，找到他们第一个公共节点public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null) {return null;}if(headB == null) {return null;}int lenA = 0;int lenB = 0;//pl：代表长的链表的长度 ps ：代表短的链表的长度ListNode pl = headA;ListNode ps = headB;while(pl != null) {lenA++;pl = pl.next;}while(ps != null) {lenB++;ps = ps.next;}//求完长度pl和ps均已为null，需要返回头节点pl = headA;ps = headB;/*lenA 和 lenB的结果：lenA > lenBlenA == lenBlenA < lenB*/int len = lenA-lenB;//两个链表的差值// < 0   == 0   > 0if(len < 0) {pl = headB;ps = headA;len = lenB-lenA;}//结果：pl永远指向的是长的链表   ps永远指向短的链表   len永远是一个正数while (len != 0) {pl = pl.next;len--;}while (pl != ps) {//判定两个链表是否有交点pl = pl.next;ps = ps.next;}//可以不写，假定没有相交，那也是nullif(pl == null ) {return null;}return pl;}

10.给定一个链表判断链表是否有环

带环的链表是这样：

具体形式链表：

方法：采用快慢指针法，慢指针每走一步快指针走两步，若链表有环两支针终会相遇

参考代码：

    //判断链表是否有环public boolean hasCycle(){ListNode fast = this.head;ListNode slow = this.head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(slow == fast){break;}}if(fast == null || fast.next == null){return false;}return true;}

11.给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null

采用快慢指针法，快指针的速度为慢指针的两倍

前提假设：

相遇公式的推导：

由于每圈都是回到原点最后等价于L=X

参考代码：

    //给定一个链表，返回链表开始入环的第一个节点，若链表无环，则返回nullpublic ListNode detectCycle(){ListNode fast = this.head;ListNode slow = this.head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(slow == fast){//第一次相遇break;}}if(fast == null || fast.next == null){//没环return null;}//slow和fast是相遇的slow = this.head;//slow从起始位置开始走，fast从相遇点开始走while(fast!=slow){fast = fast.next;slow = slow.next;}return slow;}
}