1.移除链表元素
删除链表中等于给定值 val 的所有节点（原题链接）
题解思路：设置del节点从第二个节点开始往后遍历，若cur.val==val，则将该节点删除；另需设置ahead节点用于连接链表，最后考虑第一个节点是否需要删除
class Solution { public ListNode removeElements(ListNode head, int val) { if(head==null) return null; ListNode dummyNode=new ListNode(0); dummyNode.next=head; ListNode prev=dummyNode; ListNode cur=head; while(cur!=null) { //如果找到val，prev不用后移，删除以后cur完成后移 if(cur.val==val) { prev.next=cur.next; cur=cur.next; }else {//否则两者都后移 prev=prev.next; cur=cur.next; } } //注意最后返回链表的新头节点 return dummyNode.next; } }
2.反转单链表
反转一个单链表（原题链接）
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：
完成倒置，就需要将每个节点的next域指向前一个节点，但如果发生改变就找不到后一个节点了，所以需要找一个临时节点进行存储，然后再进行修改。
代码：
双指针：
class Solution { public ListNode reverseList(ListNode head) { if(head==null||head.next==null) return head; //前一个节点 ListNode prev=null; //反转节点 ListNode cur=head; //临时节点，用于存储cur节点的下一个节点 ListNode curNext=null; while(cur!=null) { //临时节点先进行存储 curNext=cur.next; //当前节点的next指向前一个节点 cur.next=prev; //前一个节点后移 prev=cur; //当前节点后移 cur=curNext; } //最后全部反转完成后，prev节点就是反转后链表的头节点 return prev; } }
递归：
class Solution { public ListNode reverseList(ListNode head) { //传递的两个参数就是需要反转的两个节点 return reverse(null,head); } private ListNode reverse(ListNode prev,ListNode cur) { if(cur==null) return prev; ListNode curNext=cur.next; cur.next=prev; prev=cur; cur=curNext; //完成后移以后递归新的反转节点 return reverse(prev,cur); } }
3.返回链表的中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点（原题链接）
题解思路：快慢指针，快指针时慢指针速度的二倍，当快指针走到链表末端时，慢指针走到链表中间，此时慢指针就是中间节点
public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null) {//当节点数为奇数时，fast走到末端，fast.next==null；为偶数时，fast==null fast=fast.next.next;//fast一次走两步 slow=slow.next;//slow一次走一步 } return slow; }
4.输出链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点（原题链接）
题解思路：该题也是通过快慢指针的方法来实现的，快指针先走k-1步，然后快慢指针一起走，当快指针走到末端时，慢指针的位置即为链表的倒数第k个节点
public ListNode FindKthToTail(ListNode head,int k) { if(k<=0)//判断k的合法性，当k<=0时，该节点不存在，直接返回null return null; ListNode fast=head; ListNode slow=head; while(k-1>0&&fast!=null) {//fast先走k-1步，且不能走出链表（此处k的合法性也有影响） fast=fast.next; k--; } if(fast==null)//若走出链表，即k不合法，返回null return null; while(fast.next!=null) {//快慢指针一起走，当快指针走到末端时，慢指针即为所求 fast=fast.next; slow=slow.next; } return slow; }
5.分割链表
编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前（原题链接）
题解思路：新建两条链表，设置cur节点从原链表头节点开始往后遍历，cur.val如果小于x，就将该节点置于第一条链表，否则就放在第二条链表，最后如果第一条链表为空，直接返回head2，否则返回head1，head2不为空是还需将两条链表进行连接
public ListNode partition(ListNode pHead, int x) { if(pHead==null||pHead.next==null) { return pHead;//链表为空，返回空；仅有一个节点就直接返回，无需比较 } ListNode cur=pHead;//cur节点遍历原链表 ListNode head1=null;//新建1链表的头节点 ListNode cur1=null;//新建1链表的遍历节点 ListNode head2=null;//新建2链表的头节点 ListNode cur2=null;//新建2链表的遍历节点 while(cur!=null) {//cur==null时，原链表完成遍历 if(cur.val<x) {//如果cur.val<x，就将cur接在新建1链表上 if(head1==null) {//第一次插入 head1=cur; cur1=cur; }else { cur1.next=cur; cur1=cur; } } else { if(head2==null) {//第一次插入 head2=cur; cur2=cur; }else { cur2.next=cur; cur2=cur; } } cur=cur.next;//插入以后，cur往后走一步，继续判断当前节点需要插入的地方 } if(head1==null) {//如果新建1链表为空，则直接返回新建2链表的头节点 return head2; } cur1.next=head2;//新建1链表不为空，则需连接两条链表 if(head2!=null)//若新建2链表也有数据，需手动将链表尾的next置为空，然后返回head1 cur2.next=null; return head1; }
6.删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针（原题链接）
题解思路：新建一条链表，把没有重复的节点接在这条链表上，最后返回这条链表的头节点
tips：这种题可设置一个虚拟节点作为新链表的头节点newHead，最后返回newHead.next，虚拟节点的存在可以减少边界情况的判断，减少思维量
public ListNode deleteDuplication(ListNode pHead) { ListNode cur=pHead;//cur节点用于遍历原链表 ListNode newHead=new ListNode(-1);//虚拟节点 ListNode tmp=newHead;//tmp节点在新链表移动，完成链表的往后连接 while (cur!=null) { 当cur.next!=nul时，才有cur.next.val，防止空指针异常 if(cur.next!=null&&cur.val==cur.next.val) {//升序链表，若两值相等则后移 while(cur.next!=null&&cur.val==cur.next.val) { cur=cur.next;//可能有多个重复节点，则需设置循环后移 } cur=cur.next;//上边完成后移后还需再后移一步，才是需要考虑是否插入的节点 }else {//如果不符合上边的条件，直接将cur节点插入新链表中 tmp.next=cur; tmp=cur; cur=cur.next; } } tmp.next=null;//若将原链表的最后一个节点也删除，则新链表的尾端还需将其next置为空，所有直接手动置为空 return newHead.next;//返回新链表的newHead.next }
7.链表的回文结构
链表的回文结构（原题链接）
形如1 2 2 1； 3 4 5 6 5 4 3；等正反顺序读取所读结果相同的结果即为回文结构
题解思路：先找到中间节点，然后将中间节点往后的节点进行倒置，再让两个节点分别从两端开始往中间走，值相等则继续往中间走，如果碰面则为回文结构
public boolean chkPalindrome(ListNode A) { if(A==null)//链表为空则直接返回false return false; if(A.next==null)//链表仅一个节点则其一定为回文结构 return true; ListNode fast=A;//此处与题三相同，找到中间节点 ListNode slow=A; while(fast!=null&&fast.next!=null) { fast=fast.next.next; slow=slow.next; } ListNode cur=slow.next;//将中间节点往后的节点进行倒置 while(cur!=null) { ListNode curNext=cur.next; cur.next=slow; slow=cur; cur=curNext; } while(A!=slow) {//两个节点从链表两端开始往中间走 if(A.val!=slow.val)//值若不同则直接返回false return false; if(A.next==slow)//若为奇数个节点，则最后A==slow，偶数个节点的最后A.next==slow return true; A=A.next; slow=slow.next; } return true; }
8.环形链表
给你一个链表的头节点 head ，判断链表中是否有环（原题链接）
题解思路：环形链表的证明需要设置快慢指针，若链表有环则两指针一定会在环中相遇，即证明有环
public boolean hasCycle(ListNode head) { if(head==null||head.next==null)//如果空链表或链表内仅一个节点，则一定无环 return false; ListNode fast=head; ListNode slow=head; while(true) { fast=fast.next.next;//快慢指针，快指针速度为慢指针二倍 slow=slow.next; if(fast==null||fast.next==null)//快指针走的快，如果快指针走出链表，则一定无环 return false; if(fast==slow)//如果两指针相遇，则一定有环 return true; } }
9.环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null（原题链接）
题解思路：依旧时利用快慢指针完成解答，根据其数学关系列出等式求解：
有环的情况下，当慢指针进入环形入口时，快指针先进入，在慢指针完成第一圈之前，快指针一定会与慢指针相遇（为什么slow走一步，fast必须一次走两步，不能走三步四步；为什么慢指针一定走不完1圈；为什么一定会相遇见下（环形链表）小总结中详解），则可以由其路程关系列出等式2（x+y）=x+n(y+z)+y,即x + y = n (y + z),让n为1（n=1的原因在下边小总结中），那么x=z，也就是说头节点到环形入口点的距离和相遇节点到环形入口点的距离相等，令两指针同时从两处开始走，当相遇时即为环形入口点所在位置.
public ListNode detectCycle(ListNode head) { if(head==null||head.next==null) {//前半部分代码与8环形链表代码相同，重点理解后半部分代码 return null; } ListNode fast=head; ListNode slow=head; while(true) { slow=slow.next; fast=fast.next.next; if(fast==null||fast.next==null) return null; if(fast==slow)//如果有环，则在两指针相遇时跳出循环 break; } fast=head;//让一个指针从head开始走，另一个指针从相遇点开始走，当两指针相遇时，所在位置即为环形入口点 while ((fast!=slow)) { fast=fast.next; slow=slow.next; } return fast; }
（环形链表）小总结
1.快慢指针速度问题： （fast一次走两步，slow一次走一步）
当慢指针进入环时，快指针一定在环中某一位置，因为两指针速度差为1，也就是相当于快指针在以1的速度来追赶慢指针，一趟移动，相对距离减少1，所以不可能漏过，肯定会相遇，若快指针一次走三步四步或者更多，两指针的相对速度就会变大，就有大概率会擦肩而过，从而导致，相遇时间加长或永远都不会相遇的情况，所以快2慢1时正确的.
2.慢指针走不完一圈相遇问题：
慢指针走完1圈，快指针一定走完2圈，又因为由1.得只要慢指针进来，两者就不会错过，所以在慢指针走完1圈之前，一定会与快指针相遇，所以得出等式2（x+y）=x+n(y+z)+y,又因为慢指针走不完一圈，所以快指针也走不完两圈，所以n等于1.
10.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的（原题链接）
题解思路：建立一个新的链表，让原来的两条链表的数值进行比较，因为两条都是升序链表，按照值的大小依次把链表的节点插入新链表末端，最后返回新链表的头（虚拟节点的下一个节点）
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { //新建链表，设置虚拟头节点和cur节点 ListNode dummyNode=new ListNode(0); ListNode cur=dummyNode; //cur1和cur2分别用来遍历两个链表 ListNode cur1=list1; ListNode cur2=list2; while(cur1!=null&&cur2!=null) { if(cur1.val<cur2.val) { cur.next=cur1; cur1=cur1.next; cur=cur.next; }else { cur.next=cur2; cur2=cur2.next; cur=cur.next; } } //一个排完了就接上另一个链表 if(cur1==null) cur.next=cur2; if(cur2==null) cur.next=cur1; return dummyNode.next; } }
11.相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。（原题链接）
题解思路：先对两个链表都完成一次遍历，计算其链表长度，让长的链表头先走两链表之差步，然后两个指针再一起走，第一次next域相同时就是相交处，如果没有相同一直走到空，说明不相交。
代码：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int countA=count(headA); int countB=count(headB); int a=countA-countB; ListNode curA=new ListNode(0); curA.next=headA; ListNode curB=new ListNode(-1); curB.next=headB; if(a>0) { while(a-->0) curA=curA.next; }else { a=-a; while(a-->0) curB=curB.next; } while(curA!=null&&curB!=null) { if(curA.next==curB.next) { return curA.next; } curA=curA.next; curB=curB.next; } return null; } private int count(ListNode head) { ListNode cur=head; int count=0; while(cur!=null) { count++; cur=cur.next; } return count; } }
个人题解习惯
博主在做这一类oj题时，个人喜欢将极端情况单独拎出来考虑，然后再考虑一般情况，尽量提高代码通过率，以下题解的代码均含博主个人习惯，读者可根据自己情况选择。
