Java 实现链表结点插入

Java 实现链表结点插入

概述

链表是一种动态数据结构，Java 中其实现可以分为单向链表、双向链表和循环链表，链表结点插入是链表的基本操作之一。下文将详细讲解 Java 实现链表结点插入的完整攻略。

步骤

1. 定义结点类

链表中每个元素都是结点，一个结点有两个属性：

• value：表示当前结点的值
• next：表示当前结点的下一个结点

Java 中可以定义一个结点类（如下所示），用来保存当前结点的值和指向下一个结点的引用。

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

2. 分析结点插入的情况

插入结点时，分为以下三种情况：

• 新结点插入到链表头部
• 新结点插入到链表尾部
• 新结点插入到链表中间

3. 实现结点插入

针对不同的插入情况，可以分别实现链表结点的插入方法。

插入到链表头部

在链表头插入结点，只需要将新结点插入到链表头部即可。具体操作如下：

public ListNode insertToHead(ListNode head, int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head;
    return newNode;
}

插入到链表尾部

在链表尾部插入结点，需首先先找到链表的尾部结点，然后再插入新结点。具体操作如下：

public ListNode insertToTail(ListNode head, int val) {
    if(head == null) {
        return new ListNode(val);
    }
    ListNode cur = head;
    while(cur.next != null) {
        cur = cur.next;
    }
    cur.next = new ListNode(val);
    return head;
}

插入到链表中间

在链表中间插入结点，首先需要找到指定插入位置的前一个结点，然后将新结点插入到该位置。具体操作如下：

public ListNode insertToPos(ListNode head, int val, int pos) {
    ListNode newNode = new ListNode(val);
    if(pos == 1) {
        newNode.next = head;
        return newNode;
    }
    int cnt = 1;
    ListNode pre = head;
    while(pre != null && cnt < pos - 1) {
        cnt++;
        pre = pre.next;
    }
    if(pre == null) {
        return head;
    }
    newNode.next = pre.next;
    pre.next = newNode;
    return head;
}

示例说明

以下是针对不同插入情况的调用示例说明。

插入到链表头部

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head = insertToHead(head, 100);
while(head != null) {
    System.out.print(head.val + " ");
    head = head.next;
}
// 输出结果为：100 1 2 3

插入到链表尾部

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head = insertToTail(head, 100);
while(head != null) {
    System.out.print(head.val + " ");
    head = head.next;
}
// 输出结果为：1 2 3 100

插入到链表中间

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head = insertToPos(head, 100, 2);
while(head != null) {
    System.out.print(head.val + " ");
    head = head.next;
}
// 输出结果为：1 100 2 3

总结

Java 实现链表结点插入的攻略分为三个步骤，包括定义结点类、分析结点插入情况和实现结点插入。在实现插入方法时，需分别考虑插入到链表头部、尾部和中间三种情况。