如何使用Java实现链表的插入、删除和反转？

用户1289394

发布于 2024-05-11 10:54:44

800

发布于 2024-05-11 10:54:44

链表是一种常见的数据结构，它由一个个节点组成，每个节点包含一个数据元素和指向下一个节点的引用。在Java中，可以使用类来表示链表节点，然后使用这些节点构建链表并实现插入、删除和反转等操作。

首先，我们创建一个ListNode类来表示链表节点，节点包含一个数据元素和一个指向下一个节点的引用。代码如下：

public class ListNode {
    public int val;
    public ListNode next;

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

接下来，我们创建一个LinkedList类来表示链表，其中包含一些方法用于插入、删除和反转操作。代码如下：

public class LinkedList {
    private ListNode head;  // 链表头节点

    public LinkedList() {
        this.head = null;
    }

    // 插入节点到链表末尾
    public void insert(int val) {
        ListNode newNode = new ListNode(val);

        if (head == null) {
            head = newNode;
        } else {
            ListNode curr = head;
            while (curr.next != null) {
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }

    // 删除特定值的节点
    public void delete(int val) {
        if (head == null) {
            return;
        }

        if (head.val == val) {
            head = head.next;
        } else {
            ListNode curr = head;
            while (curr.next != null && curr.next.val != val) {
                curr = curr.next;
            }
            if (curr.next != null) {
                curr.next = curr.next.next;
            }
        }
    }

    // 反转链表
    public void reverse() {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        head = prev;
    }

    // 打印链表元素
    public void printList() {
        ListNode curr = head;

        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // 插入节点
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);

        // 打印原链表
        System.out.println("原链表：");
        list.printList();

        // 删除节点
        list.delete(2);

        // 打印删除节点后的链表
        System.out.println("删除节点后的链表：");
        list.printList();

        // 反转链表
        list.reverse();

        // 打印反转后的链表
        System.out.println("反转后的链表：");
        list.printList();
    }
}

以上代码中，我们定义了一个LinkedList类，其中包含了插入、删除和反转等操作。具体方法如下：

insert方法用于将新节点插入链表的末尾。如果链表为空，则将新节点设置为头节点；否则，通过遍历链表找到最后一个节点，然后将新节点链接到最后一个节点的next引用上。
delete方法用于删除特定值的节点。如果链表为空，则直接返回；如果头节点是要删除的节点，则将头指针移动到下一个节点；否则，通过遍历链表找到要删除节点的前一个节点，然后将前一个节点的next引用指向要删除节点的下一个节点。
reverse方法用于反转链表。我们使用三个指针：prev表示前一个节点，curr表示当前节点，next表示下一个节点。从头节点开始，每次迭代中，将当前节点的next指向前一个节点，然后将当前节点和前一个节点都向后移动一位，直到当前节点为空。
printList方法用于打印链表元素。我们从头节点开始遍历链表，并依次打印每个节点的值。

在main方法中，我们创建了一个LinkedList对象，并对其进行了一些操作的演示。首先，我们插入了一些节点，然后打印原链表。接着，我们删除了一个节点，并打印删除节点后的链表。最后，我们对链表进行反转，并打印反转后的链表。

通过以上代码，我们实现了链表的插入、删除和反转等操作。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-05-10，如有侵权请联系 cloudcommunity@tencent.com 删除

数据