详解单链表经典OJ题-1
https://developer.aliyun.com/article/1503999
六 链表分割
问题描述：
现有一链表的头指针 ListNode head，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
链表分割前：
分割之后：
在这里要注意的是，我们还得要先定义一个cur去遍历链表，然后再利用这四个空结点将他们串起来。这里要值得注意的是对于一开始进入的as，ae，bs，be，我们需要分开讨论。
注意细节：
1 如果x的值取的合适，对于分割的链表前半部分可能是没有数据的，也就是说as=null，那么此时我们就必须返回bs（如果后半部分也为空，那就说明就是一个空链表）
2 判断完上一个之后，我们必须要让ae.next=bs，这样才能把分割的链表链接起来
3 对于分割链表，我们不可能确保最后一个元素一定是在第二部分，也有可能是在第一部分，那么这个时候就会有一个问题，那就是这个链表没有尾巴了，所以我们要把be.next置为null
具体代码实现：
//链表的分割 public static nodelist spiltist(nodelist head,int x){ nodelist as=null; nodelist ae=null; nodelist bs=null; nodelist be=null; nodelist cur=head; if (head==null)return null; while (cur!=null){ if (cur.val<x){ //第一次进入 if (as==null){ as=cur; ae=cur; }else{//不是第一次进入 ae.next=cur; ae=ae.next; } }else{ //第一次进入 if (bs==null){ bs=cur; be=cur; }else{//不是第一次进入 be.next=cur; be=be.next; } } cur=cur.next; } if (as==null){//判断前半部分是否会有数据 return bs; } ae.next=bs;//把前后两个部分拼接起来 if (bs!=null&&be.next!=null){//判断be.next是否为null，不是null，手动置为null be.next=null; } return as; }
七 删除重复结点
问题描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
删除前：
删除后：
通过以上两张图片，我们可以利用一个傀儡结点，去把那些不重复的节点给串起来，然后返回new.next就会是我们要得到的链表。
注意细节：
1 不能一眼认定，newhead.next就是head，这是不对的，因为如果一个链表为{1，1，2，3}，就可以说明这个错误的观点
2 对于傀儡结点与链表直接的联系，我们可以通过定义一个temp，让temp=newhead，当cur.val!=cur.next.val的时候，让temp.next=cur
具体代码实现如下：
//删除重复的结点 public nodelist delet(){ nodelist newhead=new nodelist(1); nodelist cur=head; nodelist temp=newhead; while (cur!=null){ 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{ temp.next=cur; cur=cur.next; temp=temp.next; } } if(temp.next!=null){ temp.next=null; } return newhead.next; }
这里要特别提一下最后的if语句，在这个代码中，如果链表为{1，2，3，3，3}，如果没有if语句那么最后重复的节点是删不去的，根据上面代码，我们要得到的就是当cur=null的时候，temp.next=null,所以在这里我们有必要在这里进行一个这样的判断。
八 链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构
例如：1->2->2->1
返回：true
一 需要利用快慢指针找到中点
二 反转链表
在反转链表中，我们需要定义一个cur，让cur.next=slow，这样就完成了当前slow所在的下一个节点的反转，我们还需要往下走，需要在定义一个curNext去记录cur的下一个节点，不然后一个节点就找不到了，我们在把slow=cur，这样就把slow往后移了一位，我们在令cur=curNext，curNext=curNext.next（这里的要注意要利用一个if语句判断一下，curNext是否为null），结合上述，最终的目的就是反转到最后一个节点（就是slow的位置要在最后一个节点上），那么我们反转节点肯定不止一个，所以我们是需要一个循环的，那么这个循环的终止条件就是cur！=null
三 判断回文结构
从反转之后的图片来看，如果是回文结构，那么此时我们slow与head同时往后走，那么就会有head与slow相遇。这里就要特别说一下，以上情况是针对奇数个节点展开的讨论，偶数节点其实也是一样的，只不过在判断时，变成head.next=slow，具体的图可以自己尝试去画一画。在代码中，我会把两种情况的总代码写出来。
代码展示
public class PalindromeList { public boolean chkPalindrome(ListNode head) { // write code here if(head==null||head.next==null)return false; //寻找中点 ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //反转链表 ListNode cur=slow.next; ListNode curNext=cur.next; while(cur!=null){ cur.next=slow; slow=cur; cur=curNext; if(curNext!=null){ curNext=curNext.next; } } //判断回文结构 while(head!=slow){ if(head.val==slow.val){ head=head.next; slow=slow.next; if(head.next==slow){ return true; } }else{ return false; } } return true; } }
九 相交链表
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
对于相交节点，我们同样采用快慢指针的做法，设headA=slow，headB=fast，从图中我们可以看出B比A长，那么我们就要定义一个整形，来表示B与A之间的长度之差，让fast多走这个差步，之后fast与slow一起走，之后就会相遇，我们就返回相遇的节点
对于所给的链表，也可以是这种，那么这个时候也不要紧，我们可以利用一个if在前一个的基础上来判断一下，如果B更长，我们就可以交换一下fast与slow的指向
具体实现代码如下：
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode slow=headA; ListNode fast=headB; int lena = 0; int lenb = 0; while(slow!=null){ lena++; slow=slow.next; } while(fast!=null){ lenb++; fast=fast.next; } slow=headA; fast=headB; int c=lenb-lena; if(c<0){ fast=headA; slow=headB; c=lena-lenb; } while(c!=0){ fast=fast.next; c--; } while(fast!=slow){ fast=fast.next; slow=slow.next; } return slow; } }
十 判断表中是否有环
对于是否成环问题，我们采用快慢指针前去解决，我们让fast一次走两步，slow一次走一步，那么slow与fast终究会相遇的，可不敢让fast走三次，如果只有两个节点，那么是永远不会相遇的
具体代码实现如下
public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null)return false; ListNode fast=head.next; ListNode slow=head; while(fast!=null&&fast.next!=null){ if(fast==slow){ return true; } slow=slow.next; fast=fast.next.next; } return false; } }
十一 环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如图我们就是要返回2这个节点，对于这种题，我们也是利用快慢指针前去解决
1 先找到fast与slow的相遇点
2 令fast与slow其中一个置为头结点的位置，两个一起走，就会走到入环的第一个节点
代码实现：
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow=head; ListNode fast=head; 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=head; while(slow!=fast){ slow=slow.next; fast=fast.next; } return fast; } }
OJ题目网址
3 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
5 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
