Java链表ListNode详解

一、链表概述

链表是一种常用的数据结构，它存储一系列元素，这些元素由指向下一个元素的指针引用连接而成。链表是由节点组成的，每个节点包含一个数据元素和一个指向下一节点的指针。

二、Java中的链表

Java语言中的链表是通过节点(Node)的方式实现的，每个节点包含三个部分，即指向下一个节点的指针next、节点值value、以及一个前驱指针prev（如果是双向链表）。

三、ListNode类

Java中的链表通常是通过ListNode类来实现的。ListNode类是一个简单的类，包含一个值val和一个指向下一个节点的指针next。

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

四、链表的创建

在Java中，可以通过常规的方式来创建一个链表，首先声明一个头节点(head)，然后在头节点后面逐个添加新节点。这里的新节点就是ListNode类的实例。

ListNode head = new ListNode(0);
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
head.next = node1;
node1.next = node2;

五、链表的遍历

链表的遍历是指按顺序依次访问链表中的所有节点。Java链表的遍历通常使用while循环，先访问头节点(head)，然后循环访问后续节点，直到访问到null节点。

ListNode head = new ListNode(0);
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
head.next = node1;
node1.next = node2;
 
ListNode cur = head;
while(cur != null) {
    System.out.println(cur.val);
    cur = cur.next;
}

六、链表的插入

链表的插入指在链表的某个位置上插入新的节点。Java中链表的插入一般有三种情况，包括在链表的头部插入节点、在链表的尾部插入节点、在链表的指定位置插入节点。

（1）在链表头插入节点

首先需要创建一个新的节点，然后将新节点的next指向原来的头节点，最后将新节点赋值给头节点。

ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;

（2）在链表尾部插入节点

遍历到链表尾部，然后在尾部添加新节点。

ListNode newNode = new ListNode(val);
ListNode cur = head;
while (cur.next != null) {
    cur = cur.next;
}
cur.next = newNode;

（3）在链表指定位置插入节点

在Java中，链表的插入是通过改变节点的指针来完成的。使用pre节点记录待插入位置的前一节点，然后先将待插入节点的next指向pre.next，再将pre.next指向待插入节点。

ListNode newNode = new ListNode(val);
ListNode pre = head;
for(int i=1; i<pos; i++){
    pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;

七、链表的删除

链表的删除是指在链表中删除指定节点。Java中链表的删除分为删除头节点、删除尾节点和删除中间节点。删除链表节点时需要分别进行内存释放处理，以避免造成内存泄漏。

（1）删除头节点

将头节点指针移向下一节点。

head = head.next;

（2）删除尾节点

找到尾节点的前一节点pre，将pre.next置为null，然后释放掉尾节点。

ListNode cur = head;
while (cur.next.next != null) {
    cur = cur.next;
}
ListNode delNode = cur.next;
cur.next = null;
delNode = null;

（3）删除中间节点

找到待删除节点的前一节点pre，先将pre.next指向待删除节点的下一节点，再释放掉待删除节点。

ListNode pre = head;
for(int i=1; i<pos; i++){
    pre = pre.next;
}
ListNode delNode = pre.next;
pre.next = delNode.next;
delNode = null;