链表常见面试题( 建议收藏！！)，2024年最新中高级java面试题及答案大全_面试题链表排重java

先自我介绍一下，小编浙江大学毕业，去过华为、字节跳动等大厂，目前阿里P7

深知大多数程序员，想要提升技能，往往是自己摸索成长，但自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！

因此收集整理了一份《2024年最新Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上Java开发知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

如果你需要这些资料，可以添加V获取：vip1024b （备注Java）

正文

代码实现：

public Node middleNode(){

Node fast = this.head;

Node slow = this.head;

while(fast != null && fast.next != null){

slow = slow.next;

fast = fast.next.next;

}

return slow;

}

4.链表中倒数第k个节点

---

题目： 在线OJ

思考：

• 创建两个指针fast、slow，均指向 head节点

• 让 fast 走 k-1步

• 然后slow 和 fast一起，一次走一步

• 当 fast 走完时，即 fast.nest 为 null 时，slow就指向倒数第k个节点

注意 k 的合法性判定

代码实现：

public Node getKthFromEnd(int k) {

//k 合法性判定

if(k <= 0){

System.out.println(“k不合法！”);

return null;

}

Node fast = this.head;

Node slow = this.head;

while(k-1 > 0){

if(fast.next != null){

fast = fast.next;

k–;

}

else {

System.out.println(“该节点不存在！”);

return null;

}

}

while(fast.next != null){

fast = fast.next;

slow = slow.next;

}

return slow;

}

5.链表分割

---

题目： 在线OJ

思考：

• 创建两个"线段"，两个线段的头 (bs、be) 尾 (as、ae) 均初始化为 null

• 定义 cur，遍历原来的单链表

• 若 cur.data < x，则放到第一个线段

若 cur.data > x，则放到第二个线段

均采用尾插法

• 当 cur 为 null 时，原来的单链表就遍历结束

• 最后将 be 和 as拼接，即：be.next = as

代码实现：

public Node partition(int x) {

Node bs = null;

Node be = null;

Node as = null;

Node ae = null;

Node cur = this.head;

while(cur != null){

if(cur.data < 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;

}

// 判断 bs是否为空，若 bs==null，返回as

if(bs == null){

return as;

}

be.next = as;

//若 bs不为 null，需进行拼接

if(ae != null){

ae.next = null;

}

//若ae不为 null，ae的next需要置为null

return bs;

}

6.删除排序链表中的重复元素

---

题目： 在线OJ

**思考：**定义一个虚拟节点来解决问题

• 首先定义一个虚拟节点newHead

• 使用 cur 遍历链表，比较 cur.data 和 cur.next.data 是否相等

• 不相等，则将 cur节点，放置虚拟节点后

• 最后返回 newHead.next 即可

代码实现：

public Node deleteDuplicates() {

//虚拟节点

Node newHead = new Node(-1);

Node cur = this.head;

Node tmp = newHead;

while(cur != null){

if(cur.next != null && cur.data == cur.next.data){

while(cur.next != null && cur.data == cur.next.data){

cur = cur.next;

}

cur = cur.next;

}

else {

tmp.next = cur;

tmp = tmp.next;

cur = cur.next;

}

}

tmp.next = null;

return newHead.next;

}

最后记得手动将 tmp.next 置为 null，否则可能陷入死循环

7.回文链表