【数据结构】单链表面试题讲解->贰

简介: 【数据结构】单链表面试题讲解->贰

🌏引言

单链表的操作算法是笔试面试中较为常见的题目。

本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _😀

🍀合并两个有序链表

🎄题目描述

将两个升序链表合并为一个新的 升序 链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。

🎋示例:

🎍解法思路

🚩建立虚拟节点

建立一个虚拟节点为newList;

建立虚拟节点的目的:

  • 既然需要合并那么肯定是需要一个头节点
  • 由于两个链表的头节点谁大谁小不知道,所以建立虚拟节点
  • 小的就与虚拟节点相连
  • 最后返回newList.next;

🚩tmp的建立

虚拟节点不便移动,需要记录当前位置,最后返回newList.next;

那我们就需要一个指针可以向后移动,连接list1与list2比较的较小值

🚩进行合并

合并思想:

  • 对list1与list2里的元素进行比较
  • 谁小就与tmp连接,然后小的list向后走一步成为新的list1,tmp向后走一步成为新的tmp
  • 依次类推进行比较
  • 比如list1的值小,就将list1与tmp相连
  • 然后list1与tmp各自向后走一步

结束条件:当list1为null或者list2wei空时

代码实现如下:

while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }

🚩链表为空

链表为空分为两种种i情况

一个链表为空

  • 只需要将另一个链表连接在tmp后面就好

两个都为空

  • 其实上述将另一链表连接在tmp就可以解决
  • 如果连接链表为null,返回的自然也就是null

🌳完整代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
         ListNode newList = new ListNode();
        ListNode tmp = newList;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tmp.next = list1;
                tmp = tmp.next;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                tmp = tmp.next;
                list2 = list2.next;
            }
        }
        if(list1 == null) {
            tmp.next = list2;
        }
        if(list2 == null) {
            tmp.next = list1;
        }
        return newList.next;
    }
}

🍀链表分割

🎄题目描述

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前

且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
    }
}

🎍示例:

🎋思路解析:

🚩链表拆分

将该链表拆分为两个链表;

  • 链表a用于存储小于x的数
  • 链表b用于存储大于x的数

最后将链表b拼接在链表a后面,返回a链表的头指针即可

🚩链表a的建立

创建a1为a链表的头指针,a2为a链表最后一个节点的指针

建立过程:

  • 对所需要分割的链表进行遍历
  • 对每一个节点的元素大小进行判断,如果小于x就进入该链表
  • 进入后对我们的a1进行判断,判断a1当前是否为null
  • 如果为null,将当前的pHead赋给a1和a2;

  • 如果不为null,将当前的pHead赋给a2.next,a2向后走一步

代码实现如下:

if (a1 == null) {
  a1 = pHead;
  a2 = pHead;
} else {
  a2.next = pHead;
  a2 = a2.next;
}

🚩链表b的建立

创建a1为a链表的头指针,a2为a链表最后一个节点的指针

创建过程与链表a同理

代码实现如下:

if (b1 == null) {
  b1 = pHead;
  b2 = pHead;
} else {
  b2.next = pHead;
  b2 = b2.next;
}

🚩链表的合并

情况考虑:

  • 链表a为null或者两者都为null
  • 这时候只需要返回b1就可以了;

  • 当a链表不为空时,b链表为空时
  • 将b1赋给a2.next,进行合并

  • 当a链表不为null时,b链表也不为null
  • b1赋给a2.next,进行合并
  • 将b2.next置为null,作为尾节点;

代码实现如下:

if (a1 == null) {
            return b1;
        }
        a2.next = b1;
        if (b1 != null) {
            b2.next = null;
        }
        return a1;

🌳完整代码实现

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode a1 = null;
        ListNode a2 = null;
        ListNode b1 = null;
        ListNode b2 = null;
        while (pHead != null) {
            if (pHead.val < x) {
                if (a1 == null) {
                    a1 = pHead;
                    a2 = pHead;
                } else {
                    a2.next = pHead;
                    a2 = a2.next;
                }
            } else {
                if (b1 == null) {
                    b1 = pHead;
                    b2 = b1;
                } else {
                    b2.next = pHead;
                    b2 = b2.next;
                }
            }
            pHead = pHead.next;
        }
        if (a1 == null) {
            return b1;
        }
        a2.next = b1;
        if (b1 != null) {
            b2.next = null;
        }
        return a1;
    }
}

⭕总结

关于《【数据结构】单链表面试题讲解->贰》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

文章知识点与官方知识档案匹配,可进一步学习相关知识

算法技能树首页概览52070 人正在系统学习中

相关文章
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
33 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
34 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
2月前
|
存储
[数据结构] -- 单链表
[数据结构] -- 单链表
26 1
|
3月前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
2月前
|
存储
【数据结构】——单链表实现
【数据结构】——单链表实现
|
2月前
|
存储
数据结构2——单链表
数据结构2——单链表
34 1
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储
数据结构(单链表)
数据结构(单链表)
18 0
|
2月前
|
存储
数据结构--单链表
数据结构--单链表
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)