数据结构 (Java 版)：链表经典面试题解析

如果给定的测试用例都大于 x 的值，需要返回 as。如果 bs 为空，尾节点 ae 会返回 bs，如果 ae 之前的地址指向之前的某个节点，就会造成链表的死循环，此时要将排列之后的链表最后一个节点手动置为 null。

完整代码见上方 Java 实现。

1.2. 链表的回文结构

第一种思路使用双引用算法，但由于单链表只能单向遍历，效率受限。第二种思路将 val 值存入数组，但空间复杂度为 O(n)。第三种思路翻转一半的链表，过程分为三步：第一步找到链表的中间部分；第二步将链表的一半进行翻转；第三步 head 从前往后，slow 从后往前，比较 head.val 是否与 slow.val 相等，直到 slow 引用与头节点相遇为止。

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;
    }
}

当链表节点为偶数时，当 head.next = slow 时，直接返回 true。

1.3. 相交链表

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

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;
    }
}