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

EMHZ • 2024-11-01 14:08 • 编程

一、什么是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指向中间节点的后一个节点即可。

原创文章，作者：EMHZ，如若转载，请注明出处：https://www.506064.com/n/147301.html