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