数据结构(Java版)第八期：LinkedList与链表(三)

专栏：数据结构(Java版)

个人主页：手握风云

目录

一、链表中的经典面试题

1.1. 链表分割

1.2. 链表的回文结构

1.3. 相交链表

1.4. 环形链表

---

一、链表中的经典面试题

1.1. 链表分割

        题目中要求不能改变原来的数据顺序，也就是如上图所示。我们先定义一个cur引用去遍历这个链表，用每个结点的val值与x进行比较，然后利用尾插的方法把结点插入进两个链表中。我们先定义bs、be、as、ae四个引用来表示两个链表的头尾，在尾插的时候需要注意，利用ae.next = node;ae = node，记录下尾结点，保证ae永远指向最后一个结点，同时be.next=as，连接上两个链表。

class ListNode{int val;ListNode next = null;public ListNode(int val) {this.val = val;}
}public class Partition {public ListNode partition(ListNode pHead, int x){ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while(cur != null){if(cur.val < x){}else{}}}
}

        代码的大体框架已经写好，这时我们需要考虑一下当第一段插入第一个节点时，第一个节点既是头又是尾。这时有需要分两种情况，第一次插入与下一次插入，来移动be引用。

        while(cur != null){if(cur.val < x){//第一次插入if(bs == null){be = bs = cur;}else {be.next = cur;be = cur;}}else{//第一次插入if(as == null){ae = as = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;

       这时的代码还存在一种我们没有想到的情况，如果给定的测试用例都大于x的值呢。这是我们就需要返回as。我们还需要分情况。

        if(bs == null){return as;}

       如果这是我们放到OJ进行测试，发现报出异常。

        这个异常的原因比较隐蔽。因为bs为空，尾节点ae会返回bs，如果ae之前的地址指向之前的某个节点，就会造成链表的死循环，此时我们要将排列之后的链表最后一个节点手动置为null。

完整代码： 

class ListNode{int val;ListNode next = null;public ListNode(int val) {this.val = val;}
}public class Partition {public ListNode partition(ListNode pHead, int x){ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;while(cur != null){if(cur.val < x){//第一次插入if(bs == null){be = bs = cur;}else {be.next = cur;be = cur;}}else{//第一次插入if(as == null){ae = as = cur;}else {ae.next = cur;ae = cur;}}cur = cur.next;}if(bs == null){return as;}be.next = as;//连接上两个链表if(as != null){ae.next = null;}return bs;}
}

1.2. 链表的回文结构

       第一种思路，我们可以使用双引用算法，一个left引用从左开始向右移动，另一个right引用从右开始向左移动。但由于这个链表是单链表，只能从一个方向遍历。

       第二种思路，把链表里的val值取出，存进一个数组中，但题目要求空间复杂度为 。

       第三种思路，翻转一半的链表。过程分为三步，第一步，找到链表的中间部分；第二步，将链表的一半进行翻转。我们在上一期中，已经实现了翻转链表和寻找链表的中间节点。

while(cur != null){curN = cur.next;cur.next = slow;slow = cur;cur = curN;
}

        利用上面的代码我们就可以来翻转链表，第三步，head从前往后，slow从后往前，比较head.val是否与slow.val相等，直到slow引用与头节点相遇为止。这里我们讨论的是奇数个节点的链表，如果是有偶数个节点的链表，那么fast为空。

       当链表的节点为偶数时，我们不能按照之前的做法，当head.next = slow时，直接返回true。

完整代码：

import java.util.Scanner;class ListNode{int val;ListNode next;public ListNode(int val) {this.val = val;}
}public class PalindromeList {public boolean chkPalindrome(ListNode A){//1、找到链表的中间节点ListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}//2、反转链表ListNode cur = slow.next;while(cur != null){ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//3、引用A与slow同时移动while(A != slow){if(A.val != slow.val){return false;}//判断偶数个节点情况if(A.next == slow){return true;}A = A.next;slow = slow.next;}return true;}
}

1.3. 相交链表

       对于链表相交的问题，我们首先要考虑明白，到底是X形相交，还是Y形相交？

       如上图所示，很明显两个链表相交之后呈Y形。要解决问题，我们同样利用双引用的算法。第一步，先求出两个链表的长度len1、len2；第二步求出两个链表的长度差len=len1-len2；第三步，让长的链表先走len步；第四步，headA与headA同时走，相遇之后就是公共交节点。

      这个题的思路其实很简单，但是其中也有一些比较麻烦的步骤。在第二步中，如果说len1<len2，那么len<0。第三步中，我们又怎么知道哪个链表更长？

class ListNode{int val;ListNode next;ListNode(int x){val = x;next = null;}
}public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB){ListNode pl = headA;//先假设链表A是长的ListNode ps = headB;//求两个链表的长度int len1 = 0,len2 = 0;while(pl != null){len1++;pl = pl.next;}while(ps != null){len2++;ps = ps.next;}pl = headA;ps = headB;//求链表的长度差int len = len1 - len2;if(len < 0){pl = headB;ps = headA;len = len2-len1;}//让pl先走len步while(len != 0){pl = pl.next;len--;}//pl与ps同时走，知道相遇。while(pl != ps){pl = pl.next;ps = ps.next;}//如果没有公共节点，直接返回nullif(pl == null){return null;}return pl;}
}

1.4. 环形链表

        快慢引用，即慢引用⼀次⾛⼀步，快引用⼀次⾛两步，两个引用从链表起始位置开始运⾏，如果链表带环则⼀定会在环中相遇，否则快引用率先⾛到链表的末尾。与现实生活中不同，两人相遇有可能是擦肩而过。而引用确实一步一步走的。

        为什么要让快引用走两步，慢引用走一步呢？我们想象一种最极限的情况，当fast刚走完一圈时，slow刚进入环内，两个引用的距离差刚好是一个环的距离。当fast与slow每走一次，它们的距离就越接近一个环。

class ListNode{int val;ListNode next;ListNode(int x){val = x;next = null;}
}public class Solution {public boolean hasCycle(ListNode head){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;}
}