本文共 5170 字，大约阅读时间需要 17 分钟。

链表的基本操作是日常数据结构应用中非常基础也是重要的内容。以下是关于链表的一些常见操作及其实现方法。

1. 创建链表

链表的创建通常是从一个头节点开始，逐步添加节点形成链式结构。在Java中，可以通过类的方法实现链表的各种操作。以下是链表的创建方法：

public void createLinkList() {
    this.head = new Node(12);
    Node node2 = new Node(22);
    Node node3 = new Node(32);
    Node node4 = new Node(42);
    this.head.next = node2;
    node2.next = node3;
    node3.next = node4;
}

2. 查找最后一个节点

链表的最后一个节点通常用来进行扩展操作，以下是实现查找最后一个节点的方法：

public Node findLastNode() {
    Node cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    return cur;
}

3. 查找倒数第二个节点

查找倒数第二个节点需要考虑链表长度的情况。以下是实现方法：

public Node findLastTwoNode() {
    Node cur = this.head;
    if (cur.next == null) {
        System.out.println("没有节点");
        return null;
    }
    if (cur.next.next == null) {
        System.out.println("只有一个节点");
        return cur;
    }
    while (cur.next.next != null) {
        cur = cur.next;
    }
    return cur;
}

4. 查找特定节点

查找特定节点可以通过遍历链表实现。以下是查找节点的方法：

public Node findNNode(int n) {
    if (this.head == null) {
        System.out.println("null");
        return null;
    }
    if (n <= 0) {
        System.out.println("n不合法");
        return null;
    }
    int size = size();
    if (n > size) {
        System.out.println("n太大了");
        return null;
    }
    Node cur = this.head;
    int count = 1;
    while (count != n) {
        cur = cur.next;
        count++;
    }
    return cur;
}

5. 链表长度查询

链表长度的查询可以通过遍历链表实现。以下是链表长度的查询方法：

public int size() {
    Node cur = this.head;
    int count = 0;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

6. 是否包含特定值

判断链表是否包含特定值可以通过遍历链表实现。以下是实现方法：

public boolean contains(int toFind) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.val == toFind) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

7. 链表遍历

链表的遍历可以使用头插法或尾插法。以下是实现方法：

public void display() {
    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

8. 头插入法

头插入法是链表操作中常见的一种插入方式。以下是实现方法：

public void addFirst(int data) {
    Node node = new Node(data);
    if (this.head != null) {
        node.next = this.head;
    }
    this.head = node;
}

9. 尾插入法

尾插入法是链表操作中另一种常见的插入方式。以下是实现方法：

public void addLast(int data) {
    Node node = new Node(data);
    if (this.head == null) {
        this.head = node;
    } else {
        Node cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}

10. 移动指定位置节点

移动指定位置节点可以通过遍历链表实现。以下是实现方法：

public Node moveIndex(int index) {
    Node cur = this.head;
    int count = 0;
    while (count != index - 1) {
        cur = cur.next;
        count++;
    }
    return cur;
}

11. 插入特定位置节点

插入特定位置节点需要考虑链表的长度。以下是实现方法：

public void addIndex(int index, int data) {
    if (index < 0 || index > size()) {
        System.out.println("插入位置不合法");
        return;
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    Node node = new Node(data);
    Node cur = moveIndex(index);
    node.next = cur.next;
    cur.next = node;
}

12. 查找前驱节点

查找前驱节点可以通过遍历链表实现。以下是实现方法：

public Node searchPrev(int key) {
    Node cur = this.head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

13. 删除特定节点

删除特定节点可以通过查找前驱节点实现。以下是实现方法：

public void remove(int key) {
    if (this.head == null) {
        return;
    }
    if (this.head.val == key) {
        this.head = this.head.next;
    }
    Node prev = searchPrev(key);
    if (prev == null) {
        System.out.println("null");
    } else {
        Node del = prev.next;
        prev.next = del.next;
    }
}

14. 删除所有指定值节点

删除所有指定值节点可以通过遍历链表实现。以下是实现方法：

public void removeAllKey(int key) {
    Node prev = this.head;
    Node cur = prev.next;
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
        } else {
            prev = cur;
        }
        cur = cur.next;
    }
    if (this.head.val == key) {
        this.head = this.head.next;
    }
}

15. 链表反转

链表反转可以通过逐个节点重新连接实现。以下是实现方法：

public Node reverseList() {
    Node cur = this.head;
    Node prev = null;
    Node newHead = null;
    while (cur != null) {
        Node curNext = cur.next;
        cur.next = prev;
        prev = cur;
        cur = curNext;
    }
    return newHead;
}

16. 合并两个有序链表

合并两个有序链表可以通过逐个比较节点值实现。以下是实现方法：

public Node mergeTwoLists(Node l1, Node l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    Node newHead = null;
    Node cur1 = l1;
    Node cur2 = l2;
    while (cur1 != null && cur2 != null) {
        if (cur1.val <= cur2.val) {
            newHead = cur1;
            cur1 = cur1.next;
        } else {
            newHead = cur2;
            cur2 = cur2.next;
        }
    }
    if (cur1 != null) {
        newHead.next = cur1;
    } else if (cur2 != null) {
        newHead.next = cur2;
    }
    return newHead;
}

这些方法涵盖了链表的基本操作，能够满足日常的链表处理需求。通过合理组合这些方法，可以实现更复杂的链表操作。