Java单链表的增删改查与面试题详解

概述

Java单链表是一种常用的数据结构，具有插入、删除、查找等基本操作。本文将为大家详细讲解Java单链表的增删改查操作以及相关面试题。

单链表的定义

单链表是一种线性表，采用链式存储结构，通过指针来实现元素之间的关联。单链表由一系列的结点（Node）组成，每个结点包含两部分：数据域和指针域。数据域存储结点的值，指针域存储下一个结点的地址。

单链表的基本操作

插入操作

单链表插入操作有两种方式：头插法和尾插法。头插法将新结点插入到链表头部，尾插法将新结点插入到链表尾部。

头插法示例

public void addFirst(int val) {
    Node newNode = new Node(val, null);
    newNode.next = head.next;
    head.next = newNode;
}

在上面的示例中，我们创建了一个新结点，并将新结点插入到链表头部。首先，我们将新结点的next指针指向原链表的头结点，接着将原链表的头结点指向新结点。

尾插法示例

public void addLast(int val) {
    Node newNode = new Node(val, null);
    if (head.next == null) {
        head.next = newNode;
    } else {
        Node tail = head.next;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = newNode;
    }
}

在上面的示例中，我们创建了一个新结点，并将新结点插入到链表尾部。首先，我们需要遍历整个链表，找到最后一个结点（即next指针为null的结点），然后将最后一个结点的next指针指向新结点。

删除操作

单链表删除操作需要知道要删除的结点的前一个结点。删除操作即将前一个结点的next指针指向要删除结点的下一个结点即可。

public void deleteNode(int val) {
    Node prev = head;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next;
            return;
        }
        prev = prev.next;
    }
}

在上面的示例中，我们遍历整个链表，找到要删除的结点的前一个结点，然后修改前一个结点的next指针即可。

修改操作

单链表修改操作需要知道要修改的结点的位置。遍历链表找到要修改的结点，然后修改该结点的值即可。

public void updateNode(int pos, int val) {
    Node p = head.next;
    int i = 0;
    while (p != null && i < pos) {
        p = p.next;
        i++;
    }
    if (p != null) {
        p.val = val;
    }
}

在上面的示例中，我们遍历链表找到要修改的结点，然后修改该结点的值即可。

查找操作

单链表查找操作需要知道要查找的值或者其所在的位置。遍历链表找到要查找的结点，然后返回该结点的值或者该结点的位置即可。

public int getVal(int pos) {
    Node p = head.next;
    int i = 0;
    while (p != null && i < pos) {
        p = p.next;
        i++;
    }
    if (p != null) {
        return p.val;
    }
    return -1;
}

public int getPos(int val) {
    Node p = head.next;
    int pos = 0;
    while (p != null && p.val != val) {
        p = p.next;
        pos++;
    }
    if (p != null) {
        return pos;
    }
    return -1;
}

在上面的示例中，我们遍历链表找到要查找的结点，然后返回该结点的值或者该结点的位置即可。

面试题详解

面试题1

如何将一个单链表按照奇偶数分别排列？

解答：可以采用双指针法，创建两个指针分别指向奇数位置和偶数位置的结点，然后将奇数位置的结点插入到一个新链表中，偶数位置的结点插入到另一个新链表中，最后将两个新链表连接起来即可。

面试题2

如何删除一个单链表中的重复结点？

解答：可以采用哈希表来记录每个结点是否出现过，遍历链表的同时判断当前结点是否出现过，若出现过则将前一个结点的next指针指向当前结点的下一个结点即可，时间复杂度为O(n)。

总结

本文介绍了Java单链表的增删改查操作和相关的面试题，希望本文能够帮助大家更好地掌握单链表的基本操作和应用。