【算法刷题】链表笔试题解析（1）

一、链表分割

题目描述：

链接：链表分割

题目分析：

这题直接处理并不好做，我们可以构建前后两个链表，将小于x值的结点放在链表a内，将其它结点放在链表b内，这样将原链表遍历完后，原链表就自然地分成了两部分，最后将两个链表拼接起来就行了。

如果你以为这题到这里就完了，那这题就不会被分在“较难题”里了

做算法题，我们一定要细心，要考虑好程序可能会面临的所有情况，仔细梳理一下，你会发现这道题主要会有四种情况：

1、给定链表为空

2、链表中的值有大于x的，也有小于x的

3、链表中所有结点的值都大于x

4、链表中所有节点的值都小于x

这时问题就很明显了，我们之前的思路只能处理第二种情况，遇到其它情况的时候就会出现问题。

比如在第三种情况下，由于没有小于x的结点，所以链表a的头尾指针都不能指向具体的结点，这时如果再通过a链表的尾节点指向b链表的方式链接，就会出现空指针异常导致程序出错了

因此我们还需要分别处理其它三种情况：

1、因为链表为空，所以不需要处理，直接返回头结点即可

3、此时a链表的头指针应该为空，只需要返回b链表的头结点即可

4、此时b链表为空，正常让a的尾结点指向b的头，直接返回头结点即可

注意：二三种情况时需要将b的尾结点的后驱结点置空，这样才能构建一个正常的单链表

代码实现：

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

二、链表的回文结构

题目描述：

链接：链表的文结构

题目分析：

有些人看到这题的第一想法可能是遍历一遍链表，将链表中的值都存在一个数组中，然后用数组的处理方法来判断是否回文，从而大大简化题目难度。

这的确是一个不错的思路，但你有没有发现题目还有以下要求：

时间复杂度为O(n),额外空间复杂度为O(1)的算法

如果你不知道什么是时间复杂度和空间复杂度的话，可以看看博主的这篇文章：博客链接

很明显，数组的空间复杂度是O(N)，不符合题目要求，出题者明显不想让你用这么粗暴的方式解题

这里博主提供一个简单的思路：

我们可以先将链表反转，然后判断两个链表相应位置上的值是否相等即可

代码实现：

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if(A==null||A.next==null){
            return true;
        }
        ListNode cur1=A.next;
        ListNode cur2=A.next;
        ListNode head=A;
        head.next=null;
        while(cur1!=null){
            cur2=cur1.next;
            cur1.next=head;
            head=cur1;
            cur1=cur2;
        }
        while(A!=null){
            if(A.val!=head.val){
                return false;
            }
            A=A.next;
            head=head.next;
        }
        return true;
    }
}

三、链表的中间节点

题目描述：

链接：链表的中间节点

题目分析：

我们可以用快慢指针的方法，定义一个快指针fast每次走两步，再定义一个慢指针每次走一步，这样在快指针遍历完链表时，慢指针就正好位于中间位置了

注意：链表的长度可能是奇数也可能是偶数，当结点数为奇数时,fast是走不到最后一个的，如果强行每次都走两步的话最后会出现空指针异常，不过仔细观察你会发现，当fast走到倒数第二位时，slow就刚好位于中间结点了，因此我们只要改变一下循环退出条件即可

代码实现：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode cur1=head;
        ListNode cur2=head;
        while(cur1 !=null&&cur1.next!=null){
            cur1=cur1.next.next;
            cur2=cur2.next;
        }
        return cur2;
    }
}

四、相交节点

题目描述：

链接：相交节点

题目分析：

如果两个链表等长的情况下，这题就非常简单了，只需要同时让指针a、b分别从两个链表的头结点出发，判断是否有结点相等即可，但显然，两个链表的长度未必是相等的。

这时我们可以先让指针a、b分别遍历两个链表，直到有一个链表被遍历完后，这时长链表指针与长链表尾结点的距离正好是两个链表长度的差值，这时再令一指针x指向长链表的头结点，再一次让之前没遍历完的指针y与新指针x进行遍历，直到老指针y指向长链表的尾结点，这时x与长链表的尾结点的距离正好等于短链表的长度，接着就可以用处理两个等长链表的方式来处理了

代码实现：

public class Solution {
        if(headA==null&&headB==null)return null;
        ListNode cur1=headA;
        ListNode cur2=headB;
        while(cur1!=null&&cur2!=null){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        if(cur1==null){
            cur1=headB;
        }else{
            cur2=headA;
        }
        while(cur1!=null&&cur2!=null){
            cur1=cur1.next;
            cur2=cur2.next;
        }
        if(cur1==null){
            cur1=headB;
        }else{
            cur2=headA;
        }
        while(cur1!=null&&cur2!=null){
            if(cur1==cur2){
                return cur1;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return null;
    }

五、返回倒数第k个节点

题目描述：

链接：返回倒数第k个节点

题目分析：

我们可以定义两个指针，先让指针1遍历链表，同时记录指针走过的步数s，当s=k时，开始让指针2从头结点开始遍历链表，当指针1指向链表的尾结点时，指针2所指向的结点就是倒数第k个结点了

注意：可能出现k值大于链表长度或k值小于零的情况，

当k<0时，题目显然是无解的，直接return-1即可

当k大于链表长度时，我们可以通过记录指针1走过的步数s的大小来判断，如果指针1遍历完链表时，s任小于k，就说明k值超过了链表的长度，直接return -1即可

代码实现：

public class Solution {
    public int kthToLast(ListNode head, int k) {
        if (k < 0) {
            return -1;
        }
        ListNode cur1=head;
        ListNode cur2=head;
        int s=0;
        while(cur1!=null){
            cur1=cur1.next;
            if(s==k){
                cur2=cur2.next;
            }else{
                s++;
            }
        }
        if(s<k){
            return -1;
        }else{
            return cur2.val;
        }
    }
}