织梦网站地图制作教程,大连华南网站制作公司,ic外贸网站建设,正规专业短期培训学校专栏#xff1a;数据结构(Java版) 个人主页#xff1a;手握风云 目录
一、链表中的经典面试题
1.1. 链表分割
1.2. 链表的回文结构
1.3. 相交链表
1.4. 环形链表 一、链表中的经典面试题
1.1. 链表分割 题目中要求不能改变原来的数据顺序#xff0c;也就是如上图所示。… 专栏数据结构(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.nextas连接上两个链表。
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第二步求出两个链表的长度差lenlen1-len2第三步让长的链表先走len步第四步headA与headA同时走相遇之后就是公共交节点。 这个题的思路其实很简单但是其中也有一些比较麻烦的步骤。在第二步中如果说len1len2那么len0。第三步中我们又怎么知道哪个链表更长
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;}//如果没有公共节点直接返回nullif(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;}
}
