目录
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
7. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
11. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null (进阶)
前言
Hellow,大家好!我是Node_Hao!熟练掌握顺序表及链表的相关操作之后,便可以适当用一些较高难度的链表笔试题巩固提高自己的知识水平,不仅是对原有知识的复习提升,更是打破自己知识舒适区的最佳方式.另外本章还会讲到双向链表的相关知识,毕竟Java的集合框架库中LinkedList底层实现就是无头双向循环链表.所以双向链表的重要性不言而喻.
一.链表面试题
1. 删除链表中等于给定值 val 的所有节点。
解题步骤:
这道题的做法类似于侦查兵探路,首先我们定义一个prev节点和cur节点,prev节点类似长官拥有删除功能,cur类似于士兵只负责探路,有危险(要删的元素)cur向前走,prev长官的指向直接跳过该元素,当cur发现安全(没有要删的元素时),prev再向前挪动.
public ListNode removeAllKey(int key) { if (head == null) { System.out.println("单链表不能为空!"); return null; } ListNode prev = head; ListNode cur = head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if (head.val == key) { head = head.next; } return head; }
2. 反转一个单链表。
由于链表得天独厚的优势,反转链表只需要改变其各个元素的指向即可,首先我们定义三个变量,三个变量各自有其作用,prev用于充当新的头结点,cur用于改变链表的指向,curNext用于cur向后移动遍历链表,因为cur在其改变指向的同时会丢失向后走的能力.三个变量的步频始终一致,当cur==null时prev刚好走到末尾成为新的头结点.
public ListNode reverseList() { if (head == null) { return null; } ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode curNext = cur.next; cur.next = prev; prev = cur; cur = curNext; } return prev;//新的头结点 }
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
这道题如果只是简单的将链表个数除以二,需要遍历链表两次,那么它必然达不到面试的难度,在面试难度下我们只能将链表遍历一次.因此我们需要用快慢指针来解决这类问题,首先定义快指针fast和慢指针slow,假设一个链表长为5,fast的速度为slow的两倍,那么相同时间内fast的路程必然是slow两倍,因此当fast走到末尾时,slow刚好走到中间位置.最后返回slow即可.那么就会产生一个问题,当链表长度为奇数是必然返回中间位置,那如果链表为偶数时,该返回什么位置呢?题目中要求的是返回第二个节点,如果面试官要求返回第一个呢?其实很简单我们只需要让fast在走的过程中为空时,不然slow继续走直接返回slow即可.
public ListNode middleNode() { ListNode faster = head; ListNode slower = head; while (faster != null && faster.next != null) { faster = faster.next.next; slower = slower.next; } return slower; }
public ListNode middleNode() { ListNode faster = head; ListNode slower = head; while (faster != null && faster.next != null) { faster = faster.next.next; if (faster==null){ return slower; } slower = slower.next; } return slower; }
4. 输入一个链表，输出该链表中倒数第k个结点。
一看到这道题我们第一时间想到的肯定是,算出链表的长度size,然后减去k,走size-k步即可,这样的话我们需要遍历链表两次.而面试难度只允许你遍历一次.此时就需要一点点数学技巧,咋们结合我下面给出的图来看.倒数第k个节点距最后一个节点k-1步,如果fast先走k-1步,那么slow与fast就相差k-1步,fast与slow一人一步走,当fast为最后一个节点时,slow自然而然就是倒数第k个节点,,此时返回slow即可.但是当我们判读k的合法性时,如果想让k不超过链表的长度我们必须遍历链表,这样就得遍历两次链表了.其实我们可以不判断k是否超过链表大小,只需要在fast移动过程中加一条循环条件,一但fast为空直接返回slow即可.
public ListNode FindKthToTail(ListNode head, int k) { if (head == null) { return null; } if (k <= 0) { return null; } ListNode fast = head; ListNode slow = head; while (k - 1 != 0 && fast != null) { fast = fast.next; if (fast == null) { return null; } k--; } while (fast.next != null) { slow = slow.next; fast = fast.next; } return slow; }
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
这道题,需要两个链表不断的比较,所以两个链表的头结点需要不断后移达到比较的效果,因此我们需要一个虚拟的头写点(傀儡节点),让之后较小的数连在它后面.当我们合并完所有节点时,只需返回虚拟头节点的下一个节点即可.
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) { ListNode newHead = new ListNode(-1);//虚拟节点 ListNode tmp = newHead; while (head1 != null && head2 != null) { if (head1.val < head2.val) { tmp.next = head1; tmp = tmp.next; head1 = head1.next; } else { tmp.next = head2; tmp = tmp.next; head2 = head2.next; } } if (head1 == null) { tmp.next = head2; } if (head2 == null) { tmp.next = head1; } return newHead.next; } }
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
这道题需要将链表分为两个部分,所以我们定义四个变量,bs,be,as,ae,分别是前半段的首尾和后半段的首尾 .经过判断依次将链表元素放入对于位置,最后再将两个链表合并.这道题有很多需要注意的情况:1.题中并没有说链表是有序排序的,所以当后半段不为空时,可能指针域为空的节点不在最后一位,所以我们需要将ae(最后一位手动置空).2.一定不要忘记链接前后两段.3.当前半段为空时直接返回后半段as即可.
public ListNode partition(ListNode pHead, int x) { ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = head; while (cur!=null){ if(cur.val<x){ if(bs==null){ bs = cur; be = cur; }else {//尾插 be.next = cur; be = be.next; } }else { if(as==null){ as = cur; ae = cur; }else {//尾插 ae.next = cur; ae =ae.next; } } cur = cur.next; } //预防第一个段为空 if (bs == null) { return as; } be.next = as;//前后两段链接 //不一定所有的数字都大于k if (as != null) { ae.next = null; } return bs; }
7. 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
这道题由于头结点也可能和下一个节点重复,所以需要一个虚拟的头结点,删除思想类似于第一题的侦察兵,cur在前面探路,prev负责删除.值得注意的是,当我们写cur向前走的循环条件时,一定要首先判断cur.next!=null,否则当判断cur.val==cur.next.val时会空指针异常.
public ListNode deleteDuplication(ListNode pHead) { if(pHead==null){ return null; } ListNode newHead = new ListNode(-1); ListNode prev = newHead; ListNode cur = pHead; while (cur!=null){ if(cur.next!=null&&cur.val==cur.next.val){ while (cur.next!=null&&cur.val==cur.next.val){ cur = cur.next; } cur = cur.next; }else { prev.next = cur; prev = prev.next; cur = cur.next; } } prev.next = null; return newHead.next; }
8. 链表的回文结构。(进阶)
这道题堪称经典一题更比三题强,被许多大厂当做面试题,有多种不同的解法,今天我分享的是一种较为容易理解的做法.做法可以概括为三句话"1.找到中间节点,2.反转后半段,3.首尾中间靠拢并判断"1.找到中间节点我们之前已经讲过,用快慢指针这里不过多赘述.2.反转后半段之前也讲过,就是逆置链表的思想.3.首尾中间靠拢并判断是否相等,此时需要注意的是当链表为偶数时,首尾就不会汇聚到同一个节点上,所以我们需要判断当head.next==slow时也跳出循环.
public boolean chkPalindrome(ListNode head) { if (head == null) { return false; } ListNode fast = head; ListNode slow = head; ListNode cur = slow.next; while (fast != null && fast.next != null) {//找到中间位置 fast = fast.next.next; slow = slow.next; } while (cur != null) {//反转链表 ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; } while (head != slow) {//判断回文 if (slow.val != head.val) { return false; } if (head.next != slow) { return true; } slow = slow.next; head = head.next; } return true; }
9. 输入两个链表，找出它们的第一个公共结点。
基于链表各个元素之间靠指针域链接的特性,两个链表之所以能够相交,一定是因为指针域相同.一但相交后面就不可能分开,所以链表相交一定是Y型.但是两个链表的长度不一定相同,所以如果我们想找到相同的节点还是得依靠快慢指针,那么快指针比慢指针多走几步呢?由图我们可以发现两个链表的后半段长度一定相等,差别就在前半段.所以我们可以分别计算出两个链表的长度,让快指针先走两个链表的长度的差值步,此时快慢指针所指向的长度一致,然后一人一步走直到相遇,返回相遇节点即可.
这道题代码看似很长,其实大部分都是计算长度,为了尽可能的少遍历链表,我先假设headA为最长的链表而pl始终指向最长的链表,当计算出的长度小于0时,我们只需交换pl和ps的指向即可.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null||headB==null){ return null; } ListNode pl = headA; ListNode ps = headB; int len1 = 0; int len2 = 0; while (pl!=null){ len1++; pl = pl.next; } pl = headA; while (ps!=null){ len2++; ps = ps.next; } ps = headB; int len = len1-len2; if(len<0){ pl = headB; ps = headA; len = len2 -len1; } while (len!=0){ pl = pl.next; len--; } while (pl!=ps){ if(pl==null||ps==null){ return null; } pl = pl.next; ps = ps.next; } return pl; }
10. 给定一个链表，判断链表中是否有环。
这道较为简单,它的作用是为下一道题打基础.判断一个链表是否有环,只需定义两个快慢指针,快指针一次走2步,慢指针一次走1步.如果两个指针能相遇那么一定存在环.如果fast在走的过程中为空那么一定不存在环.
public boolean hasCycle(ListNode head) { if (head == null) { return false; } 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; }
11. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null (进阶)
这道题略有难度,在上一题的基础上我们可以求得相遇点,由我在下图中的分析可得,让fast从起点开始,slow从相遇点开始,一人一步走,一定会在入口点相遇.此时返回入口点即可.
public ListNode detectCycle(ListNode head) { if (head == null) { return null; } ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if(fast==null||fast.next==null){ return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow;//或者fast }
二.无头双向链表的实现
无头双向链表作为,java集合框架中LinkedList的底层实现原理,其重要性不言而喻.今天我们就从最底层的逻辑来构建一个无头双向链表,并实现其基本的增删改查功能.
1.基本类的配置:
根据双向链表的基本特性,首先我们要定义定义两个基本类,一个是节点类,一个链表类.节点类中存放双向链表节点的基本属性(值域,前驱,后继),这是其面向对象的第一步.其次我们要在链表类中定义一个头结点和为节点,此时的头结点和尾结点只是一个变量,并不是真实存在.这就体现了无头双向链表的特点.最后我们只需要在链表类中构造自己需要的方法即可.
class ListNode2 {
public int val;
public ListNode2 prev;
public ListNode2 next;
public ListNode2(int val) {
this.val = val;
}
}
public class My_DoubleList {
public ListNode2 head;
public ListNode2 last;
}2.基本功能实现:
1)打印链表:
定义一个节点类型的变量,在遍历链表的同时打印链表的值即可.
public void display() {
ListNode2 cur = head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}2)获取链表的长度:
定义一个节点类型的变量和一个计数器,遍历链表的同时计数器加一即可.
public int size() {
ListNode2 cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}3)链表中是否包含某个元素:
定义一个节点类型的变量,遍历链表的同时并判断,如果cur.val==key时,返回true即可.
public boolean contains(int key) {
ListNode2 cur = head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}4)找到要删除或插入的元素:
该方法非常重要,插入或删除元素都需要调用它.基于双向链表的特性,我们不论是插入还是删除直接找到当前位置即可,不必像单项链表一样,找到前一个元素的位置.
public ListNode2 searchIndex(int index) {
if (index<0||index>size()){
System.out.println("输入位置不合法!");
return null;
}
ListNode2 cur = head;
while (index!=0){
cur = cur.next;
index--;
}
return cur;
}以上方法均为辅助功能,接下才是双向链表的真正功能.
1)头插法:
基于双向链表的特性,当链表为空时,头结点和尾结点都需要置空.当向head之前插入时需改变node.next的指向和head.prev的指向,并将head向前移动.
public void addFirst(int data) {
ListNode2 node2 = new ListNode2(data);
if (head == null) {
head = node2;
last = node2;
} else {
head.prev = node2;
node2.next = head;
head = node2;
}
}2)尾插法:
尾插与头插类似这里不过多赘述,之所以没有将node.next置空是因为,node没有初始化时前驱和后继都为null.
public void addLast(int data) {
ListNode2 node2 = new ListNode2(data);
if (head == null) {
head = node2;
last = node2;
} else {
last.next = node2;
node2.prev = last;
last = node2;
}
}3)任意位置插:
head==0时调用头插法,head==size()时调用尾插法.不属于以上两种情况时调用查找函数,接收到指定位置的元素cur.在将node与cur相互绑定即可.
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("输入位置不合法");
return;
}
if (index == 0) {
addFirst(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode2 cur = searchIndex(index);
ListNode2 node2 = new ListNode2(data);
node2.next = cur;
cur.prev.next = node2;
node2.prev = cur.prev;
cur.prev = node2;
}4)删除第一次出现的元素(key):
这道题代码看似很长其实只要搞清每个if-else之间的关系,就能很容易的写出.首先我们需要用变量cur遍历链表,第一个if-else判断cur是不是要删除的元素,如果是暂定,如果不是cur向后移.当第一个if为真时,第二个if再判断你删除的是否为头结点,如果是头结点并且头结点的下一位不为空,我们让头结点向后移即可,但如果头结点的下一位为空,我们得把last也置为空因为last是成员变量.当第二个if为假时,说明删除的不是头结点,为中间节点.但此时还要注意判断我们删除的元素是不是尾结点,如果是尾结点只需让last向后移即可.
public void remove(int key) {
ListNode2 cur = head;//局部变量
if (head == null) {
System.out.println("链表为空");
return;
}
while (cur != null) {
if (cur.val == key) {
if (head==cur) {
head = head.next;
if (head!=null){
head.prev = null;
}else {
last = null;
}
} else {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = last.prev;
}
}
return;
} else {
cur = cur.next;
}
}
System.out.println("没有你要删除的元素");
return;
}5)删除所有出现过的元素(key):
与删除一个元素方法基本一致,当删除一个元素不必跳出循环,继续删除即可.
public void removeAllKey(int key) {
ListNode2 cur = head;//局部变量
if (head == null) {
System.out.println("链表为空");
return;
}
while (cur != null) {
if (cur.val == key) {
if (cur==head) {
head = head.next;
if (head!=null){
head.prev = null;
}else {
last = null;
}
} else {
cur.prev.next = cur.next;
if (cur.next != null) {
cur.next.prev = cur.prev;
} else {
last = last.prev;
}
}
}
cur = cur.next;
}
return;
}6)清空链表:
由于head在置空过程中会迷失方向,所以定义curNext来记录head.next帮助head遍历链表.
public void clear() {
if (head==null){
return;
}
while (head!=null){
ListNode2 curNext = head.next;
head.next = null;
head.prev = null;
head = curNext;
}
last = null;
System.out.println("置空完毕");
return;
}总结
顺序表与链表的入门以及进阶内容,今天就更新完了,如果我的文章对你的学习有一点点帮助和启发记得三连哦!祝三连的帅哥美女好运连连!