1. 题目列表及链接

1. 删除链表中等于给定值 val 的所有节点。
2. 反转一个单链表。
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
4. 输入一个链表，输出该链表中倒数第k个结点。
5. .将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
7. 链表的回文结构。
8. 输入两个链表，找出它们的第一个公共结点。
9. 给定一个链表，判断链表中是否有环。
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL 。

2. 题目解析及代码

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

题目解析
这道题需要移除所有的目标节点，我们可以使用两个辅助节点 prev（前驱节点），cur（遍历节点）。prev在cur前面。开始使用cur往前遍历，当cur指向的节点不是目标节点，prev跟随cur一起往后移动一步，当cur指向的节点是目标节点，使cur继续往后遍历，prev不再往后走，并使prev的next为cur遍历后的位置。

代码示例

class Solution {public ListNode removeElements(ListNode head, int val) {//先判断传入指针是否为空if(head==null){return head;}//上面如果不判断，下面这行可能会有空指针异常ListNode cur=head.next;ListNode prev=head;//进入循环开始遍历while (cur!=null){//如果不是目标节点，prev和cur一起往后移动if (cur.val != val) {prev = cur;cur=cur.next;//这一步可以合起来，这里方便理解}else{//否则只移动cur，并把prev的next指向curprev.next=cur.next;cur=cur.next;}}//最后判断头节点是否为目标节点//这一步也可以在最前面来写，但是要以循环的方式，防止头节点一直为目标节点if(head.val==val){head=head.next;}return head;}
}

2.2 反转一个单链表

题目解析
要反转一个链表，我们采用头插法，然后一步一步往后遍历节点，将遍历到的节点（cur）的next指向头结点，并且让当前节点设置成头结点。此事我们就需要考虑，cur的next指向改变了，怎么才能让cur正常遍历完原来的链表，这时我们使用curN来指向原链表cur的next。

代码示例

class Solution {public ListNode reverseList(ListNode head) {if(head==null){//判断传入头节点是否为空return null;}//如果不加上面判断，下面这行可能引发空指针异常ListNode cur=head.next;  //使尾节点的next置nullhead.next=null;//遍历初始链表，并反转链表while(cur!=null){ListNode curN=cur.next;//防止初始链表的顺序丢失//头插cur.next=head;head=cur;//使cur的顺序回到初始链表的顺序cur=curN;}return head;}
}

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

题目解析
解法1：首先想到的是把链表的节点个数求出来，然后遍历节点个数/2次就能得到中间节点。
解法2：使用快慢指针，快指针一次走两个节点，慢指针一次走一个节点。根据经典数学问题：追击问题可以知道，快指针走的路程是慢指针的两倍，所以当快指针遍历完链表后，慢指针就刚好到链表的中间节点。

代码示例

//解法1
class Solution {public ListNode middleNode(ListNode head) {int count = size(head);ListNode cur = head;for(int i=0;i<count/2;i++,cur=cur.next){}//遍历节点个数/2次就能得到中间节点return cur;}public int size(ListNode head){//计算链表长度int count=0;ListNode cur=head;while(cur!=null){cur=cur.next;count++;}return count;}
}
//解法2
class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;//快指针ListNode slow = head;//慢指针//这里判断条件顺序不能改变//否则当fast为null时，fast.next可能会有空指针异常while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}
}

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

题目解析
给的题目保证了k的位置是合法的，但是为了严谨我们首先要判断传入的节点是否合法。（有关链表的题目都要注意传入的形参的合法性）。这题我们同样可以使用快慢指针的思想，先让快指针移动k-1个节点。然后快慢指针一起往后移动，当快指针遍历完链表，慢指针就指向链表的倒数第k个节点。
代码示例

class Solution {public int kthToLast(ListNode head, int k) {if(k<=0||head==null){//判断传入参数是否合法return -1;}ListNode fast=head;//快指针ListNode slow=head;//慢指针//快指针先走k-1for(int i=0;i<k-1;i++){fast=fast.next;if(fast==null){//链表到头了还没走完k-1个节点，k的位置就不合法return -1;}}//快慢指针一起往后移动while(fast.next!=null){//快指针遍历完结束fast=fast.next;slow=slow.next;}return slow.val;//返回慢指针的值}
}

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

题目解析
这里我们创建一个虚拟头结点，然后分别遍历两个链表，当我们去遍历每个节点的时候开始比较两个节点的值。小的那个值尾插到新头的链表。最后，如果某条链表遍历完成，另一条链表的剩余部分直接尾插。

代码示例

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1==null){//如果list1为null，返回list2return list2;}else if(list2==null){//如果list2为null，返回list1return list1;}ListNode list = new ListNode();//虚拟头结点ListNode cur = list;//辅助尾插while(true){if(list1.val<list2.val){//比较值cur.next=list1;//尾插list1=list1.next;//list1往后遍历}else{cur.next=list2;//尾插list2=list2.next;//list2遍历}cur=cur.next;//cur往后走以便下一次尾插//下面当某一条链表为null时，另一条链表的剩余部分直接尾插if(list1==null){cur.next=list2;break;}else if(list2==null){cur.next=list1;break;}}//最后虚拟头结点的next即为合并的链表return list.next;}
}

2.6 以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

题目解析
我们可以将一个链表分为两条链表，一条小于x的节点，一条大于或等于x的节点。然后分别记录两条链表的头结点和尾节点。然后将第一条链表的尾结点接入第二条链表的头结点。此时有一个特殊情况：传入链表的节点都小于x或者传入链表的节点都大于等于x。而且要注意，第二条链表的尾的next可能不指向空。
代码示例

public class Partition {public ListNode partition(ListNode pHead, int x) {if(pHead==null){//判断传入链表是否为nullreturn null;}ListNode bs=null;//第一条链表的头ListNode be=null;//第一条链表的尾（遍历）ListNode as=null;//第二条链表的头ListNode ae=null;//第二条链表的尾（遍历）ListNode cur=pHead;//遍历当前链表while(cur!=null){if(cur.val<x){//小于x的节点插到第一条链表if(bs==null){//如果头为null，将节点设置为头节点bs=be=cur;}else{//头节点部位null，尾插节点be.next=cur;be=be.next;}}else{//大于等于x的节点插到第二条链表if(as==null){//如果头为null，将节点设置为头节点as=ae=cur;}else{//头节点部位null，尾插节点ae.next=cur;ae=ae.next;}}cur=cur.next;}//特殊情况//传入链表的节点都小于x或者传入链表的节点都大于等于xif(bs==null){return as;}be.next=as;//第二条链表的尾的next可能不指向空if(as!=null){ae.next=null;}return bs;}
}

2.7 链表的回文结构

题目解析
首先利用快慢指针找到链表的中间节点，然后从中间节点往右开始进行链表的翻转。最后从两头开始往中间遍历，一个一个节点比较，直到遍历到链表的中点。

代码示例

public class PalindromeList {public boolean chkPalindrome(ListNode A) {//判断传入的链表是否为nullif(A==null){return true;}//快慢指针找到中间节点ListNode slow=A;ListNode fast=A;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}//开始翻转中间节点往右的链表ListNode cur=slow.next;while(cur!=null){ListNode curN=cur.next;cur.next=slow;slow=cur;cur=curN;}//从两头开始往中间遍历while(A!=slow){//当A==slow时，链表为奇数个节点if(slow.val!=A.val){//当遍历过程中有值不相等就不是回文链表return false;}if(A.next==slow){//当A.next==slow，链表为偶数个节点return true;}//遍历slow=slow.next;A=A.next;}//成功完成遍历，链表为回文链表return true;}
}

2.8 输入两个链表，找出它们的第一个公共结点

题目解析

tip：链表相交不可能只相交一个节点，因为节点的next只有一个。
首先我们求出两条链表的长度。然后用唱的那根链表先走差值个节点，然后两条链表一起往后走，直到相遇就说明两条链表相交且相遇节点就是首个公共节点。反之，当链表遍历完了还没有相遇，就不存在公共节点。

代码示例

public class Solution {public ListNode getIntersectionNode(ListNode head1, ListNode head2) {//如果其中一条链表为null，直接返回nullif(head1==null||head2==null){return null;}//遍历两条链表求长度ListNode cur1=head1;ListNode cur2=head2;int count1=0;int count2=0;while(cur1!=null){count1++;cur1=cur1.next;}while(cur2!=null){count2++;cur2=cur2.next;}//使指针重新指向链表头cur1=head1;cur2=head2;//让长链表先走差值步if(count1>count2){for(int i=0;i<count1-count2;i++){cur1=cur1.next;}}else{for(int i=0;i<count2-count1;i++){cur2=cur2.next;}}//两条链表同时往前走while(cur1!=null){if(cur1==cur2){//当两指针相遇就到第一个公共节点了return cur1;}cur1=cur1.next;cur2=cur2.next;}//遍历完还没有相遇就不存在公共节点return null;}
}

2.9 给定一个链表，判断链表中是否有环

题目解析
这里我们还是使用快慢指针来解题，当链表存在环时，快慢指针一定会在环种相遇。没环，快指针先走到结尾。
思考
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

代码示例

public class Solution {public boolean hasCycle(ListNode head) {//这理解不需要判断传入链表是否为null了，因为下面不会引发空指针异常ListNode fast=head;//快指针ListNode slow=head;//慢指针//循环条件顺序不能变，可能会造成空指针异常while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){//当相遇存在环return true;}}//结束循环没有相遇，不存在环return false;}
}

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

题目解析
首先我们使用快慢指针找到相遇节点。


当得到相遇节点后，使fast从新回到头，然后一起出发，再次相遇就是环的入口。
代码示例

public class Solution {public ListNode detectCycle(ListNode head) {//快慢指针开始运动ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){fast=fast.next.next;slow = slow.next;if(fast==slow){//相遇结束循环break;}}//当不是if条件使循环结束，这个链表无环if(fast==null||fast.next==null){return null;}//fast回到头fast=head;//一起运动直至相遇while(fast!=slow){fast=fast.next;slow=slow.next;}return fast;}
}