数据结构(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  
        代码的大体框架已经写好，这时我们需要考虑一下当第一段插入第一个节点时，第一个节点既是头又是尾。这时有需要分两种情况，第一次插入与下一次插入，来移动be引用。
 
        while(cur != null){
            if(cur.val  
       这时的代码还存在一种我们没有想到的情况，如果给定的测试用例都大于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  
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