您的位置:

Java实现ListNode的数据结构与算法

一、什么是ListNode?

ListNode是链表的一个重要组成部分,可以存储任意类型的数据,并且每个节点都指向下一个节点,形成了链式的结构。相比于数组,链表的插入、删除操作更加高效,但是访问元素的时间复杂度为O(n)。

二、Java实现ListNode的基本结构

class ListNode<T> {
    T val;
    ListNode<T> next; 
    public ListNode(T val) {
        this.val = val; 
        this.next = null;
    }
}

上述代码的ListNode类中,使用泛型T来表示任意类型的数据,每个节点包含一个val值和一个next指向下一个节点的引用。

三、Java实现ListNode的基本操作

1. 添加节点

public static <T>void addNode(ListNode<T> head, T val) {
    ListNode<T> newNode = new ListNode<T>(val);
    if (head == null)
        head = newNode;
    else {
        ListNode<T> temp = head;
        while (temp.next != null)
            temp = temp.next;
        temp.next = newNode; 
    }
}

该代码实现了向链表末尾添加节点的功能,如果链表为空则直接将新节点设置为头节点,否则遍历链表找到末尾,将新节点添加到链表尾部。

2. 删除节点

public static <T>void deleteNode(ListNode<T> head, T val) {
    ListNode<T> temp = head;
    ListNode<T> prev = null;
    while (temp != null && !temp.val.equals(val)) {
        prev = temp;
        temp = temp.next;
    }
    if (temp != null && prev == null)
        head = head.next;
    else if (temp != null)
        prev.next = temp.next;
}

该代码实现了删除链表中某个节点的功能,如果链表头节点即为目标节点,则将头节点指向下一个节点,否则遍历整个链表,找到目标节点的前一个节点,将其next指向目标节点的下一个节点。

3. 反转链表

public static <T>ListNode<T> reverseList(ListNode<T> head) {
    if (head == null || head.next == null)
        return head;
    ListNode<T> prev = null;
    ListNode<T> curr = head;
    while (curr != null) {
        ListNode<T> temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
}

该代码实现了反转链表的功能,使用三个指针prev、curr和temp,每次迭代将curr的next指向prev,prev和curr向后移动一位,直到curr为null为止。

四、Java实现ListNode的应用

1. 判断链表是否有环

public static <T>boolean hasCycle(ListNode<T> head) {
    if (head == null || head.next == null)
        return false;
    ListNode<T> slow = head;
    ListNode<T> fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null)
            return false;
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

该代码实现了判断链表是否有环的功能,使用快指针和慢指针同时遍历链表,如果存在环,则快指针和慢指针一定会相遇。

2. 合并两个有序链表

public static <T extends Comparable<T>>ListNode<T> mergeTwoLists(ListNode<T> l1, ListNode<T> l2) {
    ListNode<T> dummy = new ListNode<>(null);
    ListNode<T> curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val.compareTo(l2.val) <= 0) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    if (l1 != null)
        curr.next = l1;
    if (l2 != null)
        curr.next = l2;
    return dummy.next;
}

该代码实现了合并两个有序链表的功能,类似于归并排序,使用一个dummy节点和一个curr指针,将两个链表依次比较,将较小的节点加入到新链表中。

3. 删除链表中间节点

public static <T>void deleteMiddleNode(ListNode<T> head) {
    ListNode<T> slow = head;
    ListNode<T> fast = head;
    ListNode<T> prev = null;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = slow.next;
}

该代码实现了删除链表中间节点的功能,使用快指针和慢指针同时遍历链表,当快指针到达末尾时,慢指针刚好到达链表中间节点,将中间节点的前一个节点的next指向中间节点的后一个节点即可。

Java实现ListNode的数据结构与算法

2023-05-18
数据结构: C++实现常用算法及数据结构

2023-05-13
Java数据结构与算法

2023-05-11
用C++实现高效数据结构和算法

2023-05-13
使用C++实现高效数据结构和算法

2023-05-13
java方法整理笔记(java总结)

2022-11-08
Java链表ListNode详解

2023-05-18
Java数据结构学习笔记

2023-05-11
Java数据结构

2023-05-11
C++编程:掌握高效数据结构与算法实践

2023-05-13
C++ 数据结构实现

一、数据结构概述 数据结构是计算机科学的基本概念之一,是指数据的组织、管理和存储方式。在计算机科学中,数据结构是一种特殊的格式,用于组织和存储数据。数据结构可分为线性结构、树结构、图结构等不同类型。在

2023-12-08
C++函数库:快速实现常见数据结构和算法

一、背景介绍 在 C++ 的程序开发中,常常需要实现各种常见的数据结构和算法。然而,这些常见的数据结构和算法实现起来并不是很简单,会消耗程序员大量的时间和精力。为应对这一挑战,现在有许多 C++ 函数

2023-12-08
重学java笔记,java笔记总结

2022-11-23
java学习笔记(java初学笔记)

2022-11-14
印象笔记记录java学习(Java成长笔记)

2022-11-12
java笔记,尚硅谷java笔记

2022-12-01
数据库的笔记mysql,数据库管理系统笔记

2022-11-24
Java链表的实现与应用

2023-05-11
java笔记,大学java笔记

2022-11-28
golang数据结构库,golang数据结构与算法

2022-11-27