当前位置： 首页 > article >正文

【数据结构练习题】链表与LinkedList

article 2024/12/25 5:27:59

顺序表与链表LinkedList

  • 选择题
  • 链表面试题
    • 1. 删除链表中等于给定值 val 的所有节点。
    • 2. 反转一个单链表。
    • 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
    • 4. 输入一个链表，输出该链表中倒数第k个结点。
    • 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    • 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
    • 7. 链表的回文结构。
    • 8. 输入两个链表，找出它们的第一个公共结点。
    • 9. 给定一个链表，判断链表中是否有环。
    • 10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
    • 11. 删除链表中重复的结点

选择题

1
在这里插入图片描述A错误：头插不需要遍历链表，与链表长度无关
B错误：尾插不需要遍历链表，因为有一个引用指向了尾结点，可以直接插入
C错误：删除第一个节点也不需要遍历链表
D正确：删除最后一个节点之前，先要把倒数第二个节点找到，因为最后一个节点删除之后，需要将倒数第二个节点的next置为null 故需要遍历链表
因此选择D
2
在这里插入图片描述
答案：D
解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表
3
在这里插入图片描述
答案：D
解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。
4
在这里插入图片描述
在这里插入图片描述
5
在这里插入图片描述
A错误：ArrayList中的元素不一定有序，ArrayList没有要求里面的元素必须有序，可能有序也可能不有序
B正确：ArrayList中的元素可以通过下标修改
C错误：ArrayList中的元素没要求必须要唯一，可以唯一也可以重复
D错误：ArrayList中的元素是通过下标访问的，而不是通过key
故正确应该选B
6
在这里插入图片描述
A正确：ArrayList 和 LinkedList都是实现了List接口
B正确：ArrayList是动态类型顺序表，插入时当空间不足时会自动扩容
C正确：LinkedList底层是链表结构，链表不支持随机访问，如果要访问任意元素只能通过查找处理
D错误：LinkedList中插入或者删除元素，只需要修改几个引用的指向即可，不需要搬移愿意，时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移，时间复杂度O(N)

链表面试题

1. 删除链表中等于给定值 val 的所有节点。

OJ链接

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }  
        if(head.val==val){
            head=head.next;
        } 
        return head;
    }
}

2. 反转一个单链表。

OJ链接

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

OJ链接
在这里插入图片描述

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4. 输入一个链表，输出该链表中倒数第k个结点。

OJ链接
在这里插入图片描述

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = Integer.parseInt(sc.next());
            ListNode head = new ListNode(-1);
            ListNode temp = head;
          //生成链表
            for (int i = 0; i < n; i++) {
                ListNode node = new ListNode(sc.nextInt());
                temp.next = node;
                temp = temp.next;
            }
            int k = Integer.parseInt(sc.next());
          //使用快慢指针
            if(getKthFromEnd(head.next,k) != null){
                System.out.println(getKthFromEnd(head.next,k).val);
            }
            else{
                System.out.println(0);
            }
             
        }
    }
  	//通过快慢指针搜索
    public static ListNode getKthFromEnd(ListNode head,int k){
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        for(int i=0;i<k-1;i++){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}
class ListNode{
    ListNode next;
    int val;
    ListNode(int val){
        this.val=val;
        next=null;
    }
}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

OJ链接
在这里插入图片描述

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead=new ListNode();
        ListNode tmpHead=newHead;
        while(list1!=null&&list2!=null){
            if(list1.val>list2.val){
                tmpHead.next=list2;
                list2=list2.next;
            }else{
                tmpHead.next=list1;
                list1=list1.next;
            }
            tmpHead = tmpHead.next;
        }
        if(list1!=null)
            tmpHead.next=list1;
        if(list2!=null)
            tmpHead.next=list2;
        return newHead.next;
    }
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

OJ链接
在这里插入图片描述
有个易错不容易注意到：如果ae.next!=null链表会循环 此时应该将ae.next=null
在这里插入图片描述
还要设想所有数都会大于x的可能，此时会bs==null 直接return as即可

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) {
        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){
                    bs=be=cur;
                }else{
                    be.next=cur;
                    be=cur;//或be=be.next;
                }
            }else{
                if(as==null){
                    as=ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;//或ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //第一个段没有数据
        if(bs==null)
            return as;
        be.next=as;
        //防止最大的数据不是最后一个
        if(ae!=null)
            ae.next=null;
        return bs;
    }
}

7. 链表的回文结构。

OJ链接
在这里插入图片描述
若偶数时 则循环到最后head.next==slow即可确定true

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        ListNode slow=head;
        ListNode fast=head;
        //用快慢指针确定链表中点
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
		
		//翻转后段链表
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while(head!=slow){
            if(head.val!=slow.val)
                return false;
            if(head.next==slow) //偶数 head和slow不会相遇时
                return true;
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
}

8. 输入两个链表，找出它们的第一个公共结点。

OJ链接
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //分别求2个链表的长度
        ListNode pL=headA;
        ListNode pS=headB;
        int lenA=0;
        int lenB=0;
        while(pL!=null){
            lenA++;
            pL=pL.next;
        }
        while(pS!=null){
            lenB++;
            pS=pS.next;
        }
        pL=headA;
        pS=headB;
        //保证pL指向最长的链表，pS指向最短的链表，len>0
        int len=lenA-lenB;
        if(len<0){
            pL=headB;
            pS=headA;
            len=lenB-lenA;
        }

        //2.让最长的链表先走差值步
        while(len!=0){
            pL=pL.next;
            len--;
        }

        //3.就是相遇的点
        while(pL!=pS){
            pL=pL.next;
            pS=pS.next;
        }
        return pL;
    }
}

9. 给定一个链表，判断链表中是否有环。

OJ链接

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

  • 为什么快指针每次走两步，慢指针走一步可以？
    假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
  • 快指针一次走3步，走4步，…n步行吗？
  • 在这里插入图片描述
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
         if(head==null)
            return false;//可以不写
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow)
                return true;
        }
        return false;
    }
}

10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

OJ链接

  • 结论
    让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
  • 证明
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    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 fast;
    }
}

11. 删除链表中重复的结点

OJ链接在这里插入图片描述
易忽略的点：应将手动将tmpHead.next置空防止后边到最后一个节点都是重复节点
在这里插入图片描述

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode cur=pHead;
        ListNode newHead=new ListNode(-1);
        ListNode tmpHead=newHead;
        //遍历每一个节点
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                //一直让cur走到不重复的节点 
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }                    
                cur=cur.next;
            }else{
                //把这个节点加入到不重复链表中
                tmpHead.next=cur;
                tmpHead=tmpHead.next;
                cur=cur.next;
            }

        }
        //手动将tmpHead.next置空防止后边到最后一个节点都是重复节点 
        tmpHead.next=null;
        return newHead.next;
    }
}

http://www.kler.cn/a/450295.html

相关文章：

  • window安装TradingView
  • I.MX6U 启动方式详解
  • 【Qt】对象树（生命周期管理）和字符集(cout打印乱码问题)
  • Windbg常用命令
  • 五种msvcr100.dll丢失的解决方法，有效修复msvcr100.dll丢失错误！跟msvcr100.dll错误问题说拜拜！
  • 为什么要用云电脑玩游戏？5大好处揭秘，ToDesk云机性能强又易用
  • 华中电子展（OVC）︱2025 武汉国际半导体产业与电子技术博览会：引领未来“芯”科技
  • AIDD - 人工智能药物设计 - 在 Docker 上创建和运行 PostgreSQL + RDKit 卡带环境
  • Java实现Excel带层级关系的数据导出功能
  • 最新高性能多目标优化算法：多目标麋鹿优化算法（MOEHO）求解TP1-TP10及工程应用---盘式制动器设计，提供完整MATLAB代码
  • List 集合安全操作指南：避免 ConcurrentModificationException 与提升性能
  • 模型高效微调方式
  • Mysql-索引数据结构选择合理性
  • KingbaseES(金仓数据库）入门学习
  • 如何在 Ubuntu 22.04 服务器上安装 Jenkins
  • 【LuaFramework】LuaFramework_UGUI_V2框架学习
  • 精彩回顾｜在2024全球智博会 Semantic Kernel 开发者日中国站开启企业全智能化应用场景
  • 【超详细实操内容】django的身份验证系统之用户登录与退出
  • 转型云，转型AI，转型大模型，微软为什么如此人间清醒？
  • iClient3D for Cesium在Vue中快速实现场景卷帘
  • 202411 第十六届蓝桥杯青少组 STEMA 考试真题 汇总
  • JavaScript--WebAPI查缺补漏
  • 绿盟CSSP靶场-挂载虚拟化磁盘
  • Android Bootable Recovery 中的 `freecache.cpp` 文件详解
  • Java成长之路（一）--SpringBoot基础学习--SpringBoot代码测试
  • iDP3复现代码数据预处理全流程（二）——vis_dataset.py