• 技术文章 >Java >java教程

    Java数据结构之单链表与OJ题

    WBOYWBOY2022-11-24 21:26:49转载113
    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于数据结构的相关内容,包括了单链表与OJ题,下面一起来看一下,希望对大家有帮助。

    php入门到就业线上直播课:进入学习

    推荐学习:《java视频教程

    1、什么是链表?

    链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

    通俗点,就是每个元素是一个节点,然后用一个指针域给后面的节点连起来,第一个节点没有前驱,最后一个节点没有后继。

    实际中要实现的链表的结构非常多样,以下情况组合起来就有8种链表结构:

    1. 单向、双向 2. 带头、不带头 3. 循环、非循环

    我们重点讲解单向非循环链表和双向非循环链表,同时这两个也是笔试中考的比较多的。

    2、实现一个单向非循环链表

    2.1 实现前的约定

    因为链表的每个元素是一个节点,所以我们采取内部类的方式,而我们还需要定义一个头节点的引用,来始终指向头节点。

    public class MySingleList {
        private ListNode head; //引用头节点
        // 链表每个元素是一个节点
        private class ListNode {
            private int val; //存放数据元素
            private ListNode next; //存放下一个节点地址
            //构造方法
            public ListNode(int val) {
                this.val = val;
            }
        }
    }

    注意:链表最少有两个域,分别是数据域和指针域,当然你也可以有多个数据域和指针域。

    我们还需要实现以下几个常用的方法:

    public void addFirst(int data); //头插法
    
    public void addLast(int data); //尾插法
    
    public boolean addIndex(int index,int data); //任意位置插入,第一个数据节点为0号下标
    
    public boolean contains(int key); //查找关键字key是否在单链表当中
    
    public void remove(int key); //删除第一次出现关键字为key的节点
    
    public void removeAllKey(int key); //删除所有值为key的节点
    
    public int size(); //得到单链表的长度
    
    public void clear(); //清空链表

    2.2 addFirst 方法

    public void addFirst(int data) {
        ListNode newNode = new ListNode(data); //把传过来的值放到新的节点中
        newNode.next = this.head; //新节点的next指向头节点
        this.head = newNode; //使新节点成为头节点
    }

    因为head默认是指向空的,当链表为null,也不影响这个代码的执行,不信你下来画画图咯。

    2.3 addList 方法

    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        // 如果链表为空的情况
        if (this.head == null) {
            this.head = newNode;
            return;
        }
        // 先找到最后一个节点
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    2.4 addIndex 方法

    //任意位置插入,第一个数据节点为0号下标
    private ListNode findIndexPrevNode(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public boolean addIndex(int index,int data) {
        // 判断index下标的有效性
        if (index < 0 || index > size()) {
            return false;
        }
        // 如果在0下标插入则是头插
        if (index == 0) {
            addFirst(data); //头插
            return true;
        }
        // 如果在末尾插入则是尾插
        if (index == size()) {
            addLast(data); //尾插
            return true;
        }
    
        ListNode newNode = new ListNode(data); //新节点
        // 在中间插入
        ListNode prevNode = findIndexPrevNode(index); //找到index下标的前一个节点
        newNode.next = prevNode.next; //新节点的next被改为index的位置的节点
        prevNode.next = newNode; //index位置前一个节点next被改成新节点
        return true;
    }

    这个代码我们首先需要找到index下标的前一个节点,先让新节点跟index位置的节点绑定起来,在把index的前一个节点与新节点连起来,这个地方说文字是不清楚的,小伙伴们可以下来按照我这个代码画图就能理解了,也可也直接看博主之前的C语言实现数据结构专栏,那里面有图解哈。

    2.5 contains 方法

    //查找关键字key是否在单链表当中
    public boolean contains(int key) {
        // 当链表为空的情况
        if (this.head == null) {
            return false;
        }
        ListNode cur = this.head;
        // 遍历列表
        while (cur != null) {
            if (cur.val == key) {
                return true; //找到了返回true
            }
            cur = cur.next;
        }
        return false; //找不到返回false
    }

    思路很简单,遍历一遍链表,找到 cur 为空位置,如果有返回true,没有返回false,交给小伙伴自己下来画图咯。

    2.6 remove 方法

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            return;
        }
        ListNode cur = this.head;
    
        // 如果删除的是key为头节点
        if (this.head.val == key) {
            this.head = head.next;
            return;
        }
    
        // 这里不能是cur!=null, 不然会越界!!!
        while (cur.next != null) {
            // 找到 key 的前一个节点
            if (cur.next.val == key) {
                //当前的cur为key的前一个节点
                cur.next = cur.next.next; //cur链接到key的后一个节点
                return;
            }
            cur = cur.next;
        }
    }

    这里我们需要找到key的前一个节点,然后进行跟key后面的节点绑定即可,当key对应节点没人引用了,则会被自动回收掉。

    2.7 removeAllKey 方法

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }
        // 采用前后指针的方法
        ListNode cur = this.head;
        ListNode prev = this.head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next; //跳过key节点指向下一个节点
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        // 判断第一个节点是不是key
        if (this.head.val == key) {
            this.head = this.head.next; //head指向下一个节点
        }
    }

    这里大家伙先自己看看,后面讲解OJ题会有这道题详解的。

    2.8 size 和 clear 方法

    我相信这两个方法就不需要多说了吧?遍历?直接头指针置null?这不就简单了吗,这里就不写了哈,交给各位了!

    3、单链表OJ题深度解剖

    这个才是今天的重头戏,不是篮球哥不画图,是因为前面的图太简单了,小伙伴们结合着代码也能自己画出来,但是,对于OJ题,大家伙下去还是得画图的,相信看完这几道题,你会爱上数据结构的。

    3.1 移除链表元素(来源:LeetCode 难度:简单)

    题目:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

    这个题我们可以用前后指针的思路来做,这样也比较通俗易懂,更适合初学者,大概的思路是这样的:我们可以定义一个cur和first的引用,如果碰到相等,也就是first.val == val,我们则让cur的next指向first的下一个节点,如果不相等,则让cur走到first的位置,最后first往后走一步,图解:

    这里还没有完,如果第一个节点的值也是val呢?所以最后我们别忘了进行一个判断,那么最终的代码是这样的:

    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode first = head;
        while (first != null) {
            if (first.val == val) {
                cur.next = first.next;
            } else {
                cur = first;
            }
            first = first.next;
        }
        // 判断头节点的值是否也是val
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    3.2 反转链表(来源:LeetCode 难度:简单)

    题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

    这个题我们可以先取到头节点,后续的节点都进行头插法即可?我们取到头节点,并且先将头节点的next置空,但是这样一来,就找不到后面的节点了,所以我们还需要有一个curNext引用来记录要反转节点的下一个节点:

    我们的思路是这样的:首先找到头节点的next置空,cur走到curNext位置,curNext往前走,使得cur位置的next指向头节点,头节点cur再次成为新的头节点,当curNext走到null的时候循环结束。

    public ListNode reverseList(ListNode head) {
        // 空链表的情况
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode curNext = cur.next;
        head.next = null;
        while (curNext != null) {
            cur = curNext;
            curNext = curNext.next;
            cur.next = head;
            head = cur;
        }
        return head;
    }

    3.4 链表中倒数第k个节点

    题目:输入一个链表,输出该链表中倒数第k个结点。

    这个题也是很简单的一道题,可以采用前后指针法,先让first指针走k步,走完之后slow和first一起走,这样slow和first之间就相差了k步,当first为null时,slow就是倒数第k个节点,在这个过程中,我们还要判断k的合法性,如果k小于等于0?或者k大于链表的长度呢?于是我们就能写出如下的代码:

    public ListNode FindKthToTail(ListNode head,int k) {
        // 判断k的合法性
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode first = head;
        ListNode slow = head;
        // 先让first走k步
        while (k != 0) {
            // k的长度大于链表的长度
            if (first == null) {
                return null;
            }
            first = first.next;
            k--;
        }
        // 一起走,当first为null,slow就是倒数第k个节点
        while (first != null) {
            first = first.next;
            slow = slow.next;
        }
        return slow;
    }

    3.6 链表分割(来源:牛客网 难度:较难)

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

    这个题的思路我们可以这样做,既然是按照给定的值x进行分割,那么我们设定两个盘子,盘子A放小于x的节点,盘子B放大于x的节点,最后把这两个盘子的节点连起来,放回盘子A的头节点即可!

     public ListNode partition(ListNode pHead, int x) {
            if (pHead == null) {
                return null;
            }
            ListNode headA = null;
            ListNode headB = null;
            ListNode curA = null;
            ListNode curB = null;
            ListNode cur = pHead;
            while (cur != null) {
                if (cur.val < x) {
                    // 第一次放入A盘子
                    if (headA == null) {
                        headA = cur;
                        curA = cur;
                    } else {
                        curA.next = cur;
                        curA = cur;
                    }
                } else {
                    // 第一次放入B盘子
                    if (headB == null) {
                        headB = cur;
                        curB = cur;
                    } else {
                        curB.next = cur;
                        curB = cur;
                    }
                }
                cur = cur.next;
            }
            // 如果A盘子为空
            if (headA == null) {
                return headB;
            }
            curA.next = headB;
            // 避免B盘子尾节点形成环
            if (headB != null) {
                curB.next = null;
            }
            return headA;
        }

    3.7 链表的回文结构(来源:LeetCode 难度:较难)

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

    给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

    这个题有要求的,要求空间复杂度为O(1),并且还得在O(n)的时间复杂度下,那我们就原地解决这个题,我们可以分为三个步骤,首先找到中间节点,然后把中间节点往后的节点进行反转,最后左右两个指针同时往中间走。如果光看下面代码看不懂,可以结合着代码画图才能理解更透彻哦!

    public boolean chkPalindrome(ListNode A) {
        if (A == null) {
            return false;
        }
        // 只有一个节点的情况
        if (A.next == null) {
            return true;
        }
        // 首先找到中间节点
        ListNode first = A;
        ListNode slow = A;
        while (first != null && first.next != null) {
            first = first.next.next;
            slow = slow.next;
        }
        // 走到这,slow是链表的中间节点,采用头插法反转slow后续的节点
        first = slow.next;
        ListNode cur = slow;
        while (first != null) {
            cur = first;
            first = first.next;
            cur.next = slow; //链接前一个节点
            slow = cur; //更新头节点的位置
        }
        // 走到这,反转完毕,cur指向最后一个节点,让slow等于A,往中间找
        slow = A;
        while (slow != cur) {
            if (slow.val != cur.val) {
                return false;
            }
            // 偶数的情况下需要特殊判断
            if (slow.next == cur) {
                return true;
            }
            slow = slow.next;
            cur = cur.next;
        }
        return true;
    }

    3.8 相交链表(来源:LeetCode 难度:简单)

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

    题目数据 保证 整个链式结构中不存在环。

    注意,函数返回结果后,链表必须 保持其原始结构 。

    这个题我们可以这样做,长链表先走两个链表的长度差的步数,因为相交之后的节点都是一样的个数,所以走了差值后,就两个链表一起往后走,相等了则就是相交节点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode longList = headA; //longList始终记录长的链表
        ListNode shortList = headB;
        // 分别求出两个链表的长度
        int lenA = 0;
        int lenB = 0;
        ListNode cur = headA;
        while (cur != null) {
            lenA++;
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            lenB++;
            cur = cur.next;
        }
        int len = lenA - lenB;
        // 如果B链表长于A链表
        if (len < 0) {
            // 修正相差长度
            len = lenB - lenA;
            longList = headB; //longList始终记录长的链表
            shortList = headA;
        }
        // 让长链表先走差值len步,然后同步走,相等了即为相交节点
        while (len != 0) {
            longList = longList.next;
            len--;
        }
        while (longList != shortList) {
            longList = longList.next;
            shortList = shortList.next;
        }
        // 如果两个链表走到了null,则没有中间节点返回null,如果有,返回任意一个即可
        return longList;
    }

    推荐学习:《java视频教程

    以上就是Java数据结构之单链表与OJ题的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:CSDN,如有侵犯,请联系admin@php.cn删除

    前端(VUE)零基础到就业课程:点击学习

    清晰的学习路线+老师随时辅导答疑

    自己动手写 PHP MVC 框架:点击学习

    快速了解MVC架构、了解框架底层运行原理

    专题推荐:java
    上一篇:详细介绍Java正则表达式之单字符匹配和预定义字符 下一篇:自己动手写 PHP MVC 框架(40节精讲/巨细/新人进阶必看)

    相关文章推荐

    • ❤️‍🔥共22门课程,总价3725元,会员免费学• ❤️‍🔥接口自动化测试不想写代码?• 一起来聊聊JavaScript的事件委托、判断URL是否合法及全排列• 实例JavaScript之实现数值的动态变化• 浅析JavaScript中的程序控制流和函数• JavaScript进阶学习之初识类、函数进阶、如何改变this指向• java的特点是什么
    1/1

    PHP中文网