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指向中間節點的後一個節點即可。