【算法刷题】链表笔试题解析（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 hereif(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 hereif(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;}}
}