完全搞懂链表的常见的问题以及解法
写在前面
链表一直都是一个优秀码农必须要熟练掌握的数据结构之一，关于链表的使用以及题型非常多并且复杂，我打算在这篇文章里逐渐记录我自己遇到的所有相关的问题以及解决方法，并不一定每一个类型都会有对应的代码示例，比较简单的就只写一个思路了哦，感兴趣的同学可以一起。
一、单向链表
1、判断单向链表是否时回文链表
什么是回文链表，也就是不论从前往后还是从后往前看，这个链表的数据顺序都是一样的。（ex：1->2->3->2->1）
两种解法，第一种是利用一个辅助栈 。
这个Stack里面直接按照遍历的顺序存入每一个链表的节点，遍历完一遍之后，根据Stack先进后出的特性，依次弹出栈内的元素，自然就可以形成一个逆序的链表，同时每弹出一个元素就跟原链表进行对比，如果完全相同那么就是回文链表。（这种解法的缺点就是需要一个额外的栈空间，对于空间复杂度不友好）
public static boolean solution1(Node head){
Stack
Node current = head;
while(current != null){
stack.push(current);
current = current.next;
}
while(head != null){
if (head.value != stack.pop().value){
return false;
}
head = head.next;
}
return true;
}
第二种解法 ，快慢指针。
快慢指针是处理链表相关问题一个比较好的方法，通过设置两个指针，pointA每次移动一个单位，pointB每次移动两个单位，那么理论上来说当pointB移动到链表的结尾的时候，pointA刚好走到链表的中间部分；当pointA到达中间位置后，往后的每一步我们都将当前的链表进行一个逆序的操作（ex：原链表是这样的：1->2->3->2->1，那么在逆序后变成这样：1->2->3<-2<-1）；然后我们再从链表的开头和结尾的地方同时开始向中间遍历，就能得到我们要的结果。（如果节点个数是奇数个，那么就是上面例子里的情况，提前将中间节点3指向null，最后两个方向过来的指针同时指向null那么遍历就结束了；如果是偶数个，我们可以记录下链表的长度，到达中间位置的时候手动停止）最后不要忘记将进行了逆序操作的半截链表还原。（可以直接使用对比时使用的头指针接着向后走重新链接链表）。那么此时我们就可以不需要额外的空间来辅助我们了。
public static boolean solution2(Node head){
if (head == null || head.next == null){
return true;
}
Node n1 = head;
Node n2 = head;
while(n2.next != null && n2.next.next != null){//找中点
n1 = n1.next;
n2 = n2.next.next;
}
n2 = n1.next;
n1.next = null;
Node n3 = null;
while(n2 != null){//反转右半部分的链表
n3 = n2.next;
n2.next = n1;
n1 = n2;
n2 = n3;
}
n3 = n1;
n2 = head;
boolean result = true;
while(n1 != null && n2 != null){//验证每一个对应的位置是不是一样的
if (n1.value != n2.value){
result = false;
break;
}
n1 = n1.next;
n2 = n2.next;
}
n1 = n3.next;//从这里开始往下都是重新把逆序的右半部分重新逆序回来
n3.next = null;
while(n1 != null){
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return result;
}
2、将单向链表按照某值划分成左边小，中间相等，右边大的形式
看起来有点难度但是实际上只需要有限个变量就可以了；
我们设置六个变量，分别是：小于区域的左右边界，等于区域的左右边界，大于区域的左右边界；现在我们假设有这样一个链表：4->6->3->5->8->5->2，我们给定一个特殊值：5，下面开始具体的操作：
我们先看如何将三个区域的数据分离开：
首先我们来到第一个节点发现value = 4，比目标值5小，那么小于区域的左右边界（ShortHead，后面简写为SH；ShortTail，后面简写为ST）SH和ST全部指向这个value = 4的节点；接着我们向后移动，发现当前节点的value = 6，比5大，那么大于区域的左右边界（BigHead，BigTail）BH和BT都指向当前节点；继续移动来到value = 3的地方，发现也小于5；因为此时SH和ST已经有了指向的位置，那么说明在此之前已经发现过小于目标值5的节点了，所以我们将ST指向当前value为3的节点，同时将SH指向ST；这也就等同于将原本的value = 4的第一个节点指向了当前value = 3的这个节点；继续走来到第四个节点发现value刚好等于5，并且它还是第一个值等于5的节点，所以将等于区域的左右边界（EqualHead，EqualTail）EH和ET更改为指向当前这个节点；再来到下一个节点value = 8，大于5，并且发现它不是第一个大于5的节点，所以操作流程和之前的第三步一样；之后一个节点的value = 5，和目标值一样，并且不是第一个值等于5的节点，操作方法也和第三步一样；
接下来是如何将这已经划分好的三个区域链接起来，其实很简单，只要按照SH->ST->EH->ET->BH->BT的顺序将这几个节点重新链接，就能够得到最后的结果。
是不是觉得很简单啊，那你就错啦。我们还需要额外考虑一个问题，这三部分是否存在，要不然就会出现链接null的情况导致报错咯。
public static Node listPartition(Node head, int aim){
Node SH = null;
Node ST = null;
Node EH = null;
Node ET = null;
Node BH = null;
Node BT = null;
Node next = null;
while(head != null){
next = head.next;
head.next = null;
if (head.value < aim){
if (SH == null){
SH = head;
ST = head;
} else {
ST.next = head;
ST = head;
}
} else if (head.value == aim){
if (EH == null){
EH = head;
ET =head;
} else {
ET.next = head;
ET = head;
}
} else if(head.value > aim){
if (BH == null){
BH = head;
BT = head;
} else {
BT.next = head;
BT = head;
}
}
head = next;
}
if(ST != null){//判断是否有小于区域
ST.next = EH;
ET = ET == null ? ST : ET;
}
if (ET != null){
ET.next = BH;
}
return SH != null ? SH : (EH != null ? EH : BH);
}
3、判断两个单向链表是否相交，相交的话返回第一个相交的节点
分为两种情况来看，一种是单向链表无环，一种有环；
首先是无环的情况：
那么这就是非常简单的老问题了，直接看看代码怎么写吧各位
public static Node noLoop(Node head1, Node head2){
if (head1 == null || head2 == null){
return null;
}
Node current1 = head1;
Node current2 = head2;
int n = 0;
while(current1 != null){
n++;
current1 = current1.next;
}
while(current2 != null){
n--;
current2 = current2.next;
}
if(current1 != current2){//判断当前两个链表的尾巴是否是同一个，不是的话直接返回空，说明不相交
return null;
}
current1 = n > 0 ? head1 : head2; // 判断到底原先的两个链表谁长,长的变成current1
current2 = current1 == head1 ? head2 : head1; // 短的变成current2
n = Math.abs(n);
while(n != 0){//让长的先多走相差的步数
n--;
current1 = current1.next;
}
while(current1 != current2){
current1 = current1.next;
current2 = current2.next;
}
return current1;
}
其次是有环的情况：
到这里我们要稍微的分类讨论一下了；第一种情况，两个链表都有环，但是他们不相交；第二种情况，两个链表都有环，并且它们的入环节点是同一个；第三种情况，两个链表都有环，但是入环节点不一样。
对于第二种情况，因为入环节点一样，所以我们可以直接将这一情况归入无环链表相交的问题中，同样是长的链表先把相差的步数走完，然后两个链表一起出发，发现当前的入环节点loop1==loop2后直接返回loop1。
对于剩下两种情况则要稍微复杂一点；虽然入环的节点不一样，但是此时由于它们都是单向链表，所以一定是共用环，那么直接让loop1持续走，如果在loop1转回到自己之前没有遇到loop2，那么就是第一种有环但不相交的情况，如果遇到了就是有环相交但是入环节点不同。
public static Node getLoopNode(Node head){//通过快慢指针找环
if (head == null || head.next == null || head.next.next == null) return null;//要成环，作为单链表最少都要有三个节点
Node slowPoint = head.next;
Node fastPoint = head.next.next;
while(slowPoint != fastPoint){
if (fastPoint.next == null || fastPoint.next.next == null) return null;
fastPoint = fastPoint.next.next;
slowPoint = slowPoint.next;
}
fastPoint = head;
while (slowPoint != fastPoint){
slowPoint = slowPoint.next;
fastPoint = fastPoint.next;
}
return slowPoint;
}
public static Node getIntersectNode(Node head1, Node head2){
if (head1 == null || head2 == null){
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null){//如果没环走noLoop，也就是上一个单独的代码
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null){
return bothLoop(head1, head2, loop1, loop2);
}
return null;
}
public static Node bothLoop(Node head1, Node head2, Node loop1, Node loop2){
Node current1 = null;
Node current2 = null;
if (loop1 == loop2){//有环并且入环一样
current1 = head1;
current2 = head2;
int n = 0;
while(current1 != loop1){
n++;
current1 = current1.next;
}
while(current2 != loop2){
n--;
current2 = current2.next;
}
current1 = n > 0 ? head1 : head2; // 判断到底原先的两个链表谁长,长的变成current1
current2 = current1 == head1 ? head2 : head1; // 短的变成current2
n = Math.abs(n);
while(n != 0){//让长的先多走相差的步数
n--;
current1 = current1.next;
}
while(current1 != current2){
current1 = current1.next;
current2 = current2.next;
}
return current1;
} else {//有环但入环不一样
current1 = current1.next;
while(current1 != loop1){
if (current1 == loop2){
return loop1;
}
current1 = current1.next;
}
return null;
}
}
持续更新。。。。