首页 / JAVA / Java带头节点单链表的增删融合以及是否有环

Java带头节点单链表的增删融合以及是否有环

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java带头节点单链表的增删融合以及是否有环，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5802字，纯文字阅读大概需要9分钟。

内容图文

带头节点单链表

1.优势：

1）当链表为空时，指针指向头结点，不会发生null指针异常

2）方便特殊操作（删除第一个有效节点或者插入一个节点在表头）

3）单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。

4）代码更加简单易懂

2.相关操作

1）建立单链表即建立一个头结点

   static class Entry<T> {
        T data; // 链表节点的数据域
        Entry<T> next; // 下一个节点的引用

        public Entry(T data, Entry<T> next) {
            this.data = data;
            this.next = next;
        }

    }

    /**
     * 头节点的类型
     *
     * @param <T>
     */
    private static class HeadEntry<T> extends Entry<T> {
        int cnt; // 用来记录节点的个数

        public HeadEntry(int cnt, T data, Entry<T> next) {
            super(data, next);
            this.cnt = cnt;
        }
    }

2）头插：新建节点next域指向头结点的next域，再将头结点next指向新节点。

  
    public void insertHead(T val) {
        Entry<T> newNode = new Entry<>(val, null);
        newNode.next = this.head.next;
        this.head.next = newNode;
    }

3）尾插：从头结点开始遍历，当next出现null时，已经到达尾部，将next指向新节点即可

    public void insertTail(T val) {
        Entry<T> temp = this.head;
        Entry<T> newNode = new Entry<>(val, null);
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

4）删除值为val的节点：设置一前一后指针进行遍历，当后指针发现值为val的节点时，前指针的next域指向后指针的next域即可

    public void remove(T val) {
        Entry<T> frontTemp = this.head;
        Entry<T> temp = frontTemp.next;
        while (temp.data != val) {
            frontTemp = frontTemp.next;
            temp = temp.next;
        }
        frontTemp.next = temp.next;
    }

5）逆置单链表 :将第二个有效节点不断进行头插操作，就会产生逆置效果

将链表从第二个有效节点开始一分为二，不断头插进前一链表

public void reverse() {
        if (this.head.next == null) {
            return;
        }
        Entry<T> cur = this.head.next.next;
        this.head.next.next = null;
        Entry<T> post = null;
        while (cur != null) {
            post = cur.next;
            cur.next = head.next;
            head.next = cur;
            cur = post;
        }
    }

6）获取倒数第k个节点的值：设置两个相距K的指针，当前指针到达链表尾部时，前指针指向倒数第k个节点

 public T getLastK(int k) {
        Entry<T> cur1 = this.head.next;
        Entry<T> cur2 = cur1.next;
        for (int i = 1; i < k; i++) {
            cur2 = cur2.next;
            if (cur2 == null) {
                return null;
            }
        }
        while (cur2 != null) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1.data;
    }

7）判断链表是否有环，如果有，返回入环节点的值；否则返回null：

设置快慢指针，快指针一次移动两次，慢指针一次移动一次，如果出现快指针指向的节点等于慢指针指向的节点，即证明节点有环。

入环节点的求法：fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点

 public T isLinkCircle() {
        //利用快慢指针检测是否有环
        Entry<T> slow = this.head.next;
        Entry<T> quick = this.head.next;
        while (quick != null && quick.next != null) {
            slow = slow.next;
            quick = quick.next.next;
            if (slow == quick) {
                break;
            }
        }
        if (quick == null) {
            return null;
        } else {
            // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点
            quick = this.head.next;
            while (quick != slow) {
                quick = quick.next;
                slow = slow.next;
            }
            return slow.data;
        }
    }

总源代码

class Link<T extends Comparable<T>> {

    // 指向单链表的第一个节点
    Entry<T> head;

    public Link() {
        this.head = new Entry<>(null, null);
    }

    /**
     * 单链表的头插法
     *
     * @param val
     */
    public void insertHead(T val) {
        Entry<T> newNode = new Entry<>(val, null);
        newNode.next = this.head.next;
        this.head.next = newNode;
    }

    /**
     * 单链表的尾插法
     *
     * @param val
     */
    public void insertTail(T val) {
        Entry<T> temp = this.head;
        Entry<T> newNode = new Entry<>(val, null);
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    /**
     * 单链表中删除值为val的节点
     *
     * @param val
     */
    public void remove(T val) {
        Entry<T> frontTemp = this.head;
        Entry<T> temp = frontTemp.next;
        while (temp.data != val) {
            frontTemp = frontTemp.next;
            temp = temp.next;
        }
        frontTemp.next = temp.next;
    }

    /**
     * 逆置单链表
     */
    public void reverse() {
        if (this.head.next == null) {
            return;
        }
        Entry<T> cur = this.head.next.next;
        this.head.next.next = null;
        Entry<T> post = null;
        while (cur != null) {
            post = cur.next;
            cur.next = head.next;
            head.next = cur;
            cur = post;
        }
    }

    /**
     * 获取倒数第K个单链表节点的值
     * 1.遍历一次链表，统计链表节点的个数length
     * 2.length-k
     * 只遍历一次链表，找出数
     *
     * @param k
     */
    public T getLastK(int k) {
        Entry<T> cur1 = this.head.next;
        Entry<T> cur2 = cur1.next;
        for (int i = 1; i < k; i++) {
            cur2 = cur2.next;
            if (cur2 == null) {
                return null;
            }
        }
        while (cur2 != null) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1.data;
    }

    /**
     * 判断链表是否有环，如果有，返回入环节点的值；否则返回null
     *
     * @return
     */
    public T isLinkCircle() {
        //利用快慢指针检测是否有环
        Entry<T> slow = this.head.next;
        Entry<T> quick = this.head.next;
        while (quick != null && quick.next != null) {
            slow = slow.next;
            quick = quick.next.next;
            if (slow == quick) {
                break;
            }
        }
        if (quick == null) {
            return null;
        } else {
            // fast从第一个节点开始走，slow从快慢指针相交的地方开始走，它们相遇的时候，就是环的入口节点
            quick = this.head.next;
            while (quick != slow) {
                quick = quick.next;
                slow = slow.next;
            }
            return slow.data;
        }
    }

    /**
     * 打印单链表的所有元素的值
     */
    public void show() {
        Entry<T> temp = this.head.next;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }


    /**
     * 单链表的节点类型
     *
     * @param <T>
     */
    static class Entry<T> {
        T data; // 链表节点的数据域
        Entry<T> next; // 下一个节点的引用

        public Entry(T data, Entry<T> next) {
            this.data = data;
            this.next = next;
        }

    }

    /**
     * 头节点的类型
     *
     * @param <T>
     */
    private static class HeadEntry<T> extends Entry<T> {
        int cnt; // 用来记录节点的个数

        public HeadEntry(int cnt, T data, Entry<T> next) {
            super(data, next);
            this.cnt = cnt;
        }
    }

    /**
     * 合并两个有序的单链表
     *
     * @param link
     */

    public void merge(Link<T> link) {
        Entry<T> p = this.head;
        Entry<T> p1 = this.head.next;
        Entry<T> p2 = link.head.next;

        // 比较p1和p2节点的值，把值小的节点挂在p的后面
        while (p1 != null && p2 != null) {
            if (p1.data.compareTo(p2.data) >= 0) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        if (p1 != null) { // 链表1还有剩余节点
            p.next = p1;
        }

        if (p2 != null) { // 链表2还有剩余节点
            p.next = p2;
        }
    }
}

View Code

内容总结

以上是互联网集市为您收集整理的Java带头节点单链表的增删融合以及是否有环全部内容，希望文章能够帮你解决Java带头节点单链表的增删融合以及是否有环所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/798050.html

来源：【匿名】

【上一篇】java – 有没有办法配置Struts绑定null而不是空String？【下一篇】JAVA/JSP学习系列之五

更多 ►

【Java带头节点单链表的增删融合以及是否有环】教程文章相关的互联网学习教程文章

十二、双向链表的java实现【图】

原理图：运行结果： Node代码：public class Node { int data; Node next; Node previous; //前向指针 public Node(int value) { // TODO Auto-generated constructor stub this.data = value; } public void display() { System.out.print(data+ " "); }} doubleLinklist:public class doubleLinklist { private Node first; private Node last; //尾结点 public doubleLinklist(...

大话数据结构（八）Java程序——双向链表的实现【代码】

线性链表——双向链表双向链表定义：双向链表（double linked list): 是在单表单的每个结点中，再设置一个指向前驱结点的指针域。因此，在双向链表中的结点都有两个指针域，一个指向前驱，一个指向后继。双向链表的存储结构typedef struts DulNode{Element data;Struct DulNode *prior;前驱指针Struct DulNode *next;后继指针}DulDouble, *DulLinkList;双向链表的插入与删除双向链表的插入：假设结点为s,要将结点插入到结点p和p->n...

JavaScript 链表定义【代码】

Java记录 -48- Java数据结构-链表【代码】【图】

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。650) this.width=650;" src="/upload/getfiles/default/2022/11/13/20221113033539468.jpg" title="QQ图片20151101081241.png" />单向节点Node实例：public class NodeTest { public static void main(String[] args){ Node no...

JavaScript算法系列之-----------------链表反转（JS实现）【代码】

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。之前一直对JS实现链表理解不了，被算法大牛指点了一下豁然开朗。function ListNode(x){this.val = x;this.next = null; } 在JS中，this.val代表当前节点的值，this.next指向下一个节点，若this.next为null(对象)，则说明该节点为链表的最后一个节点。PS：把下一个节点赋值给当前对象的next属性，通过这样的方式连接。通过代码：function printListFromTailToHead(h...

【LeetCode-面试算法经典-Java实现】【082-Remove Duplicates from Sorted List II（排序链表中删除重复元素II）】【代码】【图】

【082-Remove Duplicates from Sorted List II（排序链表中删除重复元素II）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题　　Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. 题目大意　　给定一个排好序的单链表，删除所有重复...

JAVA数据结构--LinkedList双向链表【代码】

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点...

Java 模拟双端链表

双端链表：双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear这样在链尾插入会变得非常容易，只需改变rear的next为新增的结点即可，而不需要循环搜索到最后一个节点所以有insertFirst、insertLast删除链头时，只需要改变引用指向即可；删除链尾时，需要将倒数第二个结点的next置空，而没有一个引用是指向它的，所以还是需要循环来读取操作/*** 双端链表* @author stone*/ public class TwoEndpointList...

Java链表

//如果链表的的数据类型是对象，则关于比较的方法全部改成compare() //class Book{ // private String title; // private double price; // public Book(String title,double price){ // this.title = title; // this.price = price; // } // public String toString(){ // return "图书名称： " + this.title + "，价格： " + this.price; // } // public boolean compare(Bo...

23. 合并K个升序链表（学习了java的自定义比较类）【代码】【图】

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6链接：https://leetcode-cn.com/problems/merge-k-sorted-lists这是目前唯一一题能想到的hard题了，没有用到什么特别高深的思想，就是一把梭！...

Java实现双链表

public class DoubleLink<T> {//存放第一个指针private Node<T> firstNode;//存放最后一个指针private Node<T> lastNode;//存放链大小private int size;//构造函数public DoubleLink() {}// --------------------------------add（）系列----------------------------------public void addFirst(T data) {linkFirst(data);}public void addLast(T data) {linkLast(data);}public void add(T data) {linkLast(data);}public void l...

单链表的java实现

链表是由一组任意的存储单元存储线性表的数据单元，链表由两部分组成：结点（数据域）、指针域。整个链表的存取必须从头指针开始，头指针指向第一个结点，最后一个结点指向为空。java中没有指针概念，但是java中有引用，可以用引用代替指针。下面是我写的一个例子：package com.test.linked;public class newlinkList {public class Node{private Object data;private int index;private Node next;public Node(int index,Object d...

【单链表】快慢指针原理-Java语言【代码】

1.结点类package blog;/*** @Description: 结点类* @author: liuqiang* @Date: 2018/12/28 23:33*/publicclass Node {public String data; // 结点的数据域public Node next; // 结点的指针域public Node() {}// 构造方法时给data赋值public Node(String data) {this.data = data;}} 2.单链表类package bolg;/*** @Description: 单链表类* @author: liuqiang* @Date: 2018/12/28 23:38*/publicclass LinkList {private Node head; ...

两两交换链表中的节点(java实现)【代码】

题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例:给定 1->2->3->4, 你应该返回 2->1->4->3. 这个题不是简单的数字交换，而是节点之间的交换。代码如下：/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode s...

JAVA-初步认识-常用对象API(集合框架-数组和链表)【图】

一.重点介绍ArrayList和LinkedList查询快慢的原因，两者增删快慢已经介绍过了。数组是一个连续的空间，放置在堆内存中，数组里面放置着元素。讲解数组的查询为什么快(都是相对而言)，为什么链表查询慢。堆内存中，很多数据都是随机放置的，但是如果某一部分是以数组的形式存放时，里面存放的都是角标。在连续的部分上进行查询，速度快于在众多随机的位置上查找。但是如果是增删的话，那么对数组的操作则是牵一发而动全身，整体的都...

首页 / JAVA / Java带头节点单链表的增删融合以及是否有环

Java带头节点单链表的增删融合以及是否有环

内容导读

内容图文

内容总结

内容备注

内容手机端

【Java带头节点单链表的增删融合以及是否有环】教程文章相关的互联网学习教程文章

十二、双向链表的java实现【图】

大话数据结构（八）Java程序——双向链表的实现【代码】

JavaScript 链表定义【代码】

Java记录 -48- Java数据结构-链表【代码】【图】

JavaScript算法系列之-----------------链表反转（JS实现）【代码】

【LeetCode-面试算法经典-Java实现】【082-Remove Duplicates from Sorted List II（排序链表中删除重复元素II）】【代码】【图】

JAVA数据结构--LinkedList双向链表【代码】

Java 模拟双端链表

Java链表

23. 合并K个升序链表（学习了java的自定义比较类）【代码】【图】

Java实现双链表

单链表的java实现

【单链表】快慢指针原理-Java语言【代码】

两两交换链表中的节点(java实现)【代码】

JAVA-初步认识-常用对象API(集合框架-数组和链表)【图】

JAVA - 相关标签

链表 - 相关标签

JAVA - 技术教程分类

JAVA - 最新教程

JAVA - 最热教程