Java实现单链表的操作

Java实现单链表的操作攻略

单链表是一种常见的数据结构，它由节点构成，每个节点都包含了一个值和指向下一个节点的指针。本文将详细讲解如何在Java中实现单链表的操作。

节点类的定义

我们先定义一个节点类，包含了一个值和一个指向下一个节点的指针。在Java中可以使用类来实现节点：

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

其中val表示节点存储的值，next表示指向下一个节点的指针。

链表的基本操作

插入节点

在单链表中，我们可以在表头或表尾插入节点，也可以在中间插入节点。下面是三种插入节点的方法。

在表头插入节点

在链表的表头插入节点，只需要将新节点的next指向原来的头结点，然后将新节点设置为新的头结点即可。

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

在表尾插入节点

在链表的表尾插入节点，需要找到链表的尾节点，然后将尾节点的next指向新节点。

public ListNode insertAtTail(ListNode head, int val) {
    ListNode newTail = new ListNode(val);
    if (head == null) { // 链表为空
        return newTail;
    }
    ListNode tail = head;
    while (tail.next != null) { // 找到尾节点
        tail = tail.next;
    }
    tail.next = newTail; // 将尾节点的next指向新节点
    return head;
}

在中间插入节点

在链表的中间插入节点，需要找到需要插入的位置，然后将新节点的next指向该位置的后继节点，然后将该位置的前驱节点的next指向新节点。

public ListNode insertAtIndex(ListNode head, int index, int val) {
    if (index < 0) { // 无效的插入位置
        return head;
    }
    if (index == 0) { // 插入位置为表头
        return insertAtHead(head, val);
    }
    ListNode newNode = new ListNode(val);
    ListNode prev = head;
    for (int i = 0; i < index - 1; i++) { // 找到插入位置的前驱节点
        if (prev == null) {
            return head;
        }
        prev = prev.next;
    }
    if (prev == null) { // 无效的插入位置
        return head;
    }
    newNode.next = prev.next; // 将新节点的next指向后继节点
    prev.next = newNode; // 将前驱节点的next指向新节点
    return head;
}

删除节点

在单链表中，我们可以删除表头节点、表尾节点，也可以删除中间的节点。下面是三种删除节点的方法。

删除表头节点

在链表的表头删除节点，只需要将头结点的next设置为新的头结点即可。

public ListNode deleteAtHead(ListNode head) {
    if (head == null) { // 链表为空
        return null;
    }
    return head.next;
}

删除表尾节点

在链表的表尾删除节点，需要找到链表的尾节点的前驱节点，然后将前驱节点的next指向null。

public ListNode deleteAtTail(ListNode head) {
    if (head == null) { // 链表为空
        return null;
    }
    ListNode tail = head;
    ListNode prev = null;
    while (tail.next != null) { // 找到尾节点和前驱节点
        prev = tail;
        tail = tail.next;
    }
    if (prev == null) { // 链表只有一个节点
        return null;
    }
    prev.next = null; // 将前驱节点的next指向null
    return head;
}

删除中间节点

在链表的中间删除节点，需要找到需要删除的节点的前驱节点，然后将前驱节点的next指向需要删除的节点的后继节点。

public ListNode deleteAtIndex(ListNode head, int index) {
    if (index < 0) { // 无效的删除位置
        return head;
    }
    if (index == 0) { // 删除位置为表头
        return deleteAtHead(head);
    }
    ListNode prev = head;
    for (int i = 0; i < index - 1; i++) { // 找到删除位置的前驱节点
        if (prev == null || prev.next == null) {
            return head;
        }
        prev = prev.next;
    }
    if (prev == null || prev.next == null) { // 无效的删除位置
        return head;
    }
    prev.next = prev.next.next; // 将前驱节点的next指向后继节点
    return head;
}

遍历链表

遍历链表可以使用循环或递归的方式，下面是两种遍历链表的方法。

循环遍历链表

循环遍历链表，只需要从头结点开始，依次遍历每一个节点即可。

public void traverse(ListNode head) {
    ListNode curr = head;
    while (curr != null) {
        System.out.print(curr.val + " ");
        curr = curr.next;
    }
    System.out.println();
}

递归遍历链表

递归遍历链表，只需要遍历当前节点和当前节点的后继节点即可。

public void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    System.out.print(head.val + " ");
    traverse(head.next);
}

示例说明

示例1：在链表中插入节点

下面是一个示例，向一个长度为3的链表中插入一个值为5的节点。

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution();
head = solution.insertAtIndex(head, 1, 5);
solution.traverse(head); // 输出1 5 2 3

我们先创建一个长度为3的链表，然后使用insertAtIndex方法在第1个位置插入值为5的节点，然后使用traverse方法遍历链表，输出链表中每个节点的值。

示例2：从链表中删除节点

下面是一个示例，从一个长度为3的链表中删除一个值为2的节点。

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution();
head = solution.deleteAtIndex(head, 1);
solution.traverse(head); // 输出1 3

我们先创建一个长度为3的链表，然后使用deleteAtIndex方法删除第1个位置的节点，值为2，然后使用traverse方法遍历链表，输出链表中每个节点的值。