数据结构(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; } //如果没有公共节点，直接返回null if(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; }}