链表的定义

链表是一种常见的数据结构，其中的元素按顺序排列，每个元素包含对下一个元素的引用。

链表的分类

单向链表：一个节点指向下一个节点。
双向链表：一个节点有两个指针域。
循环链表：能通过任何一个节点找到其他所有的节点，将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环。

代码实现

常见的链表基本操作包括：

1. 插入：向链表中插入一个新元素。
2. 删除：从链表中删除一个元素。
3. 查找：查找链表中是否存在某个元素。
4. 遍历：按顺序访问链表中的每个元素。

链表

以下是这些基本操作的Java代码演示，以单链表为例：

class ListNode {
    int val;
    ListNode next;

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

class LinkedList {
    ListNode head;

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

    // 插入操作，在链表末尾插入新节点
    public void insert(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 删除操作，删除指定值的节点
    public void delete(int val) {
        if (head == null) return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 查找操作，判断链表中是否存在某个值
    public boolean search(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 遍历操作，打印链表中的所有值
    public void traverse() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        
        // 插入操作演示
        list.insert(1);
        list.insert(2);
        list.insert(3);
        System.out.print("After inserting: ");
        list.traverse(); // 1 2 3
        
        // 删除操作演示
        list.delete(2);
        System.out.print("After deleting: ");
        list.traverse(); // 1 3
        
        // 查找操作演示
        System.out.println("Is 3 present? " + list.search(3)); // true
        System.out.println("Is 2 present? " + list.search(2)); // false
    }
}

合并

要合并两个链表，可以将一个链表的末尾连接到另一个链表的开头。以下是合并两个链表的Java代码演示：

class ListNode {
    int val;
    ListNode next;

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

class LinkedList {
    ListNode head;

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

    // 合并两个链表
    public static ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        return dummy.next;
    }

    // 遍历操作，打印链表中的所有值
    public static void traverse(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list1 = new LinkedList();
        LinkedList list2 = new LinkedList();

        // 创建链表1：1 -> 3 -> 5
        list1.head = new ListNode(1);
        list1.head.next = new ListNode(3);
        list1.head.next.next = new ListNode(5);

        // 创建链表2：2 -> 4 -> 6
        list2.head = new ListNode(2);
        list2.head.next = new ListNode(4);
        list2.head.next.next = new ListNode(6);

        System.out.print("List 1: ");
        LinkedList.traverse(list1.head); // 1 3 5
        System.out.print("List 2: ");
        LinkedList.traverse(list2.head); // 2 4 6

        ListNode mergedList = LinkedList.merge(list1.head, list2.head);
        System.out.print("Merged List: ");
        LinkedList.traverse(mergedList); // 1 2 3 4 5 6
    }
}

这个代码演示了如何合并两个有序链表，并输出合并后的链表。

去重

要对链表进行去重，可以使用一个哈希集合（HashSet）来存储已经出现过的节点值。遍历链表的同时，如果当前节点的值已经在哈希集合中存在，则将当前节点从链表中删除；否则，将当前节点的值添加到哈希集合中。以下是对链表进行去重的Java代码演示：

import java.util.HashSet;

class ListNode {
    int val;
    ListNode next;

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

class LinkedList {
    ListNode head;

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

    // 去重操作
    public void removeDuplicates() {
        if (head == null) return;

        HashSet<Integer> set = new HashSet<>();
        ListNode current = head;
        ListNode prev = null;

        while (current != null) {
            if (set.contains(current.val)) {
                // 当前节点值已经存在，删除当前节点
                prev.next = current.next;
            } else {
                // 当前节点值不存在，将值添加到哈希集合中
                set.add(current.val);
                prev = current;
            }
            current = current.next;
        }
    }

    // 插入操作，在链表末尾插入新节点
    public void insert(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 遍历操作，打印链表中的所有值
    public void traverse() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
}

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

        // 插入操作，在链表中插入一些节点，包含重复值
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(2);
        list.insert(4);
        list.insert(1);

        System.out.print("Before removing duplicates: ");
        list.traverse(); // 1 2 3 2 4 1

        // 去重操作
        list.removeDuplicates();

        System.out.print("After removing duplicates: ");
        list.traverse(); // 1 2 3 4
    }
}

这个代码演示了如何使用哈希集合去除链表中的重复元素，并输出去重后的链表。