AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】顺序表和链表OJ题

2023-08-14 80
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】顺序表和链表OJ题

顺序表相关OJ：

第1题：

打扑克牌。实现买扑克牌、洗牌和发牌操作。

题解：

class Card{
    public int rank;//牌的值
    public String suit;//花色
    public Card(int rank, String suit) {
        this.rank = rank;
        this.suit = suit;
    }
    @Override
    public String toString() {
        return " "+suit+" "+rank;
    }
}
public class CardDemo {
    public static final String[] suits = {"♣","♥","♦","♠"};
    //买牌
    public List<Card> buyCard(){
        List<Card> Cards = new ArrayList<>();
        for (int i = 1; i <= 13; i++) {
            for (int j = 0; j < 4; j++) {
                Card card = new Card(i,suits[j]);
                Cards.add(card);
            }
        }
        return Cards;
    }
    //洗牌
    public void shuffle(List<Card> Cards){
       Random random = new Random();
       //这里一定要是ards.size()-1
        for (int i = Cards.size()-1; i > 0 ; i--) {
            int index = random.nextInt(i);
            swap(Cards,index,i);
        }
    }
    private void swap(List<Card> Cards,int i,int j){
//        int tmp = Cards[i];
          Card tmp = Cards.get(i);
//        Cards[i] = Cards[j];
          Cards.set(i,Cards.get(j));
//        Cards[j] = tmp;
          Cards.set(j,tmp);
    }
    //发牌
    public List<List<Card>> play(List<Card> Cards){
        List<Card> player1 = new ArrayList<>();
        List<Card> player2 = new ArrayList<>();
        List<Card> player3 = new ArrayList<>();
        List<List<Card>> player = new ArrayList<>();
        player.add(player1);
        player.add(player2);
        player.add(player3);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                Card card = Cards.remove(0);
                player.get(j).add(card);
            }
        }
        return player;
    }
    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        List<Card> list = cardDemo.buyCard();
        System.out.println(list);
        cardDemo.shuffle(list);
        System.out.println(list);
        List<List<Card>> ret = cardDemo.play(list);
        for (int i = 0; i < ret.size(); i++) {
            System.out.println("第"+(i+1)+"个人的牌"+ret.get(i));
        }
    }
}

代码剖析：

  1. 使用swap（）；交换方法的时候要注意Cards不是数组，要使用顺序表的操作。
  2. player.get(j).add(card)；通过player.get(j)就可以知道是哪个玩家抓牌，再将抓到的牌放到自己的手中（就是顺序表中）。
  3. 有3个玩家，每个玩家的牌是一个ArrayList，再将这些牌看成是另外一个大的顺序表的元素，这个大的顺序表存放的每个元素是一个顺序表，而这个顺序表呢里面存储的是牌！

第2题：

杨辉三角。给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

题解：

public List<List<Integer>> generate(int numRows){
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    list.add(1);
    ret.add(list);
    for (int i = 1; i < numRows; i++) {
        List<Integer> row = new ArrayList<>();
        row.add(1);
        List<Integer> prev = ret.get(i-1);
        for (int j = 1; j < i; j++) {
            int num = prev.get(j)+prev.get(j-1);
            row.add(num);
        }
        row.add(1);
        ret.add(row);
    }
    return ret;
}

代码剖析：

  1. 首先需要一个大的顺序表来存储杨辉三角每一行的顺序表，这每一行的顺序表又存储着各自行的元素比如：1、4、6、4、1。
  2. 第i行的元素第j个元素就是第i-1行的第j-1元素和j元素的相加的和。

(以下共11道链表题)

链表相关OJ：

第3题：

删除第一次出现的key的值。

题解：

//删除第一次出现的元素key
public void remove(int key){
    if(head.val == key){
        head = head.next;
        return;
    }
    ListNode cur = head;
    //循环中时cur.next，如果是cur的话会空指针异常
    while(cur.next != null){
        //这里处理不了头节点
        if(cur.next.val == key){
            cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

代码剖析：

  1. 一定不能忘记处理头节点

第4题：

删除链表中所有是key的值。

题解：

//删除所有值为key的元素。只遍历了一遍！！
/*public void removeAll(int key){
    if(head ==null) return;
    ListNode cur = head;
    //会报空指针异常的错误
    while(cur.next != null){
        if(cur.next.val == key){
            cur.next = cur.next.next;
        }
        cur = cur.next;
    }
    if(head.val == key){
        head = head.next;
    }
}*/
public void removeAll(int key){
    if(head == null){
        return;
    }
    ListNode cur = head;
    ListNode prev = head;
    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;
    }
}

代码剖析：

  1. 上面有俩种做法，尽管第一种做法没有用到第3个变量，但是不能有效执行，是一个错误示范。
  2. 第二种做法是正确写法，头节点的处理一定要放到代码最后来执行，否则若有连续的相同数字在链表最前面的话，不能执行成功，例如：6、6、8、5、4删除6，如果将头节点问题放到前面，则执行结果为6、8、5、4。放到代码最后，执行结果就正常：8、5、4。

第5题：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

题解：

//反转一个单链表
public ListNode reverseList(){
    if(head == null) return null;
    if(head.next == null) return head;
    //这一步在前，执行完才能把head.next置为null
    ListNode cur = head.next;
    head.next = null;
    while(cur != null){
        ListNode curNext = cur.next;
        cur.next = head;
        head = cur;
        cur = curNext;
    }
    return head; 
}

第6题：

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

题解：

//找中间节点只遍历一次
public ListNode middle(){
    if(head == null) return null;
    if(head.next == null) return head;
    //这里用到了快慢指针
    ListNode fast = head;
    ListNode slow = head;
    //这里的判断顺序不能颠倒，一定要是 &&
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

代码剖析：

  1. 本题使用快慢指针

第7题：

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

题解：

//找倒数第k个下标的节点
/*public ListNode FindKthToTail(int k){
    if(head == null) return null;
    checkK(k);
    ListNode fast = head;
    ListNode slow = head;
    //如果让快的先走k步的话，后面的代码会空指针异常
    while(k != 0){
        fast = fast.next;
        k--;
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}*/
public ListNode FindKthToTail(int k){
    if(head == null || k <= 0) return null;
    ListNode fast = head;
    ListNode slow = head;
    while(k-1 != 0){
        fast = fast.next;
        if(fast == null){
            return null;
        }
        k--;
    }
    while(fast.next != null){
        fast = fast.next;         
        slow = slow.next;
    }
    return slow;
}

代码剖析：

  1. 先让fast走k-1步，再让fast和slow一起走，当fast.next==null时，slow所指向的就是倒数第k个节点。

第8题：

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

题解：

//    合并俩个有序链表，合并成一个有序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode newHead = new ListNode(-1);//傀儡节点
    ListNode tmp = newHead;
    while(list1 != null && list2 != null){
        if(list1.val < list2.val){
            tmp.next = list1;
            list1 = list1.next;
            tmp = tmp.next;
        }else{
            tmp.next = list2;
            list2 = list2.next;
            tmp = tmp.next;
        }
    }
    if(list1 != null){
        tmp.next = list1;
    }
    if(list2 != null){
        tmp.next = list2;
    }
    //返回的是newHead.next，不能返回newHead
    return newHead.next;
}

第9题：

现有一链表，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

题解：

//以x为基准，大于x的在后，小于x的在前
public ListNode partition(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;
    }
    //判断bs是不是空，如果是空说明前端不存在元素
    if(bs == null){
        return as;
    }
    //将前端和后端联系起来
    be.next = as;
    if(as != null){
        //将最后一个元素置为空
        ae.next = null;
    }
    return bs;
}

代码剖析：

  1. 重点判断bs能不能为空，ae必须置为空，如果不置为空有可能发生死循环。

第10题：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

题解：

//链表的回文结构
public boolean chkPalindrome(){
    if(head == null) return true;
    //找到中间位置
    ListNode fast = head;
    ListNode slow = 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){
            return true;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
}

第11题：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题解：

//找出俩个链表的公共节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
    //先求俩个链表的长度
    int lenA = 0;
    int lenB = 0;
    ListNode pl = headA;
    ListNode ps = headB;
    while(pl != null){
        lenA++;
        pl = pl.next;
    }
    while(ps != null){
        lenB++;
        ps = ps.next;
    }
    pl = headA;
    ps = headB;
    int len = lenA - lenB;
    if(len < 0){
        pl = headB;
        ps = headA;
        len = lenB - lenA;
    }
    //让长的链表先走len步
    while(len != 0 ){
        pl = pl.next;
        len--;
    }
    //再一起走，相遇的节点就是想要的答案
    while(pl != ps){
        pl = pl.next;
        ps = ps.next;
    }
    return pl;
}

代码剖析：

  1. pl代表最长的链表，ps永远是短的链表。

第12题：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

题解：

//判断链表是否有环
public boolean hasCycle(){
    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;
}
//或者
public boolean hasCycle(){
    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 false;
    }
    return true;
}

代码剖析：

  1. 本题用到快慢指针和追及问题。

第13题：

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

题解：

//链表若有环，返回入环的第一个节点，无则null
public ListNode detectCycle() {
    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;
    }
    slow = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

代码剖析：

  1. 如果起始点到入口距离为X，相遇点到入口距离为Y，环的长度为C，则 X=Y。


 

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

文章标签：
存储
索引
Perl
算法
关键词：
顺序表链表
数据结构顺序表
数据结构链表
数据结构顺序表链表
数据结构链表oj
珠江上上上
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
57 4
三三是该溜子
|
22小时前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
7 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
27天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
53 5
aliyun1622584902-46568
|
1月前
|
存储
顺序表和链表（2）
【10月更文挑战第23天】
aliyun1622584902-46568
57 2
顺序表和链表（2）
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
49 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
68 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
208 9
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
35 1
德国都芳最好
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
83 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
34 2