1.链表逆置（很核心的操作很多地方都会用到）
详细讲讲逆置操作，他的想法：之前看了很多遍都没理解，第一次的逆置（不好理解）他是为了将第一个节点指向空，然后后面才是慢慢的逆置链表
class Solution { public ListNode reverseList(ListNode head) { if(head==null){return null; } ListNode cur=new ListNode(0); //我自己设了一个头，有了头会更方便的逆置链表 cur.next=head; head=cur; ListNode p=cur.next; cur.next=null; ListNode q=null; while(p!=null){ //逆置操作 q=p.next; p.next=cur.next; cur.next=p; p=q; } return head.next; //很细节的一个点：从头的下一个节点返回，这样就相当于无头 } }
2.寻找链表中的中间节点 （核心操作2号，也很重要）
特别重要的一个问题，他会决定你理不理解中间节点
如果奇数的时候：1 2 3 4 5 这串中间节点是几（当奇数时候，奇数是最中间的点）
如果偶数的话：1 2 2 1中间节点是几（当偶数的时候中间节点，应该是能把链表均等分成两份的所以是第二个2。这样前面是1，2后面是2，1
好了最大的问题想清楚了就很好处理了。
public ListNode middleNode(ListNode head) { ListNode fast=head; ListNode slow=head; //利用快慢指针 while(fast!=null&&fast.next!=null){ //条件一定没有fast.next.next!=null fast=fast.next.next; slow=slow.next; } return slow; } //循坏的条件，偶数的情况下就应该是第二个2，自己想一想
3.倒数第k个节点 （可能很重要，练习来玩）
想一个问题：链表：1，2，3，4，5。
5个数，倒数第二个是不是正数第4个，倒数第一个，就是正数第五个，换句话说，他给我的正着数+倒着数=总数+1.
第一个解法严格来说O（2N）
public ListNode FindKthToTail(ListNode head,int k) { if(head==null||k<=0){ return null; } ListNode cur=head; int a=0; //a是用来计数，链表一共有几个节点 int b=0; //b是用来构成下面的数学关系，正着数第几个 while(cur!=null){ a++; cur=cur.next; } cur=head; while(cur!=null){ b++; if(k+b==a+1){ //k是第几个数据节点 break; //找到就退出呗 } cur=cur.next; } return cur; } }
第二种算法，O（N），快慢指针他的核心是倒数第K个节点，距离空指针差K个指针，如倒数第二个节点，距离空指针差了K个指针，那也就是说让fast先走k个节点，然后他俩一起走，这样他俩始终距离k，那么fast到了空指针，slow就是我们要求的
public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if(head==null||k<=0){ return null; } ListNode fast=head; ListNode slow=head; while(k>0){ if(fast==null){ //快指针先走K步，但不能走过了，要是倒数第6个节点 return null; //一共五个点，这种K不合理情况不行 } fast=fast.next; k--; } while(fast!=null){ slow=slow.next; //fast和slow 一起走 fast=fast.next; } return slow; } }
4.合并两个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode cur=list1; ListNode curv=list2; ListNode m=new ListNode(0); 还是创建一个新节点会更方便的插入和删除 ListNode newb=m; if(cur==null&&curv==null){ return null; } if(cur==null){ return curv; } if(curv==null){ return cur; } while(cur!=null&curv!=null){ if(cur.val<=curv.val){ newb.next=cur; //这里插入节点很容易出错，小于之后，新链表的头连接cur， cur=cur.next; //cur连接后，cur指针后移 }else { newb.next=curv; curv = curv.next; } newb=newb.next; //新链表节点后移 } if(cur==null){ newb.next=curv; } if(curv==null){ newb.next=cur; } return m.next; } }
5.链表回文（微微难）
1.首先，我们要先找中间节点：1，2，3，2，1。中间节点slow为3（如何找看前面的题）
然后以3作为头，将3后面的节点逆置，变成：1，2，3，1，2这样，slow=slow.next后，然后定义一个指针从头遍历，另一个从slow遍历，当slow为空结束
public class PalindromeList { public boolean chkPalindrome(ListNode A) { if(A==null||A.next==null){ return true; } // write code here ListNode fast=A; ListNode slow=A; ListNode now=A; while(fast!=null&&fast.next!=null){ //找中间节点 fast=fast.next.next; slow=slow.next; } ListNode cur=slow; ListNode p,q; p=cur.next; cur.next=null; while(p!=null){ //逆置 q=p.next; p.next=cur.next; cur.next=p; p=q; } cur=cur.next; while(cur!=null){ if(now.val!=cur.val){ //重新遍历，是否为回文 return false; } cur=cur.next; now=now.next; } return true; } }
6.链表分割（微微难） 首先我们思路，把整个链表分成两个部分
一个比x小，一个比x大于或者等于，并且如果不改变原来顺序，尾插是最优的选择，
小的要求比大的在前面，然后再将小的表尾连大的链表表头，这也就是为什么要分出四个，表头尾了。
public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here ListNode cur=pHead; ListNode sb=null; //smallbegin小的头 ListNode bb=null; //bigbegin大的头 ListNode be=null; ListNode se=null; while(cur!=null){ if(cur.val<x){ if(sb==null){ //小的部分没有节点，那么需要连上cur sb=cur; se=cur; } else{ se.next=cur; //尾插 se=se.next; } }else{ //相等的情况放到大的里面 if(bb==null){ bb=cur; be=cur; } else{ be.next=cur; be=be.next; } } cur=cur.next; } if(sb==null){ //如果小的那段没有，则直接返回大的那块 return bb; } se.next=bb; if(bb==null){ //如果大的那段没有，则直接返回小的那部分 return sb; } be.next=null; //这个也很关键最后需要让他指向空 return sb; //最后小的那部分是要连接大的那部分 } }
如果最后的be.next=null 不写会导致链表指针指向最后一个节点，这样链表就会有可能变成环，从而对链表的访问结果出现问题
