• 【做算法学数据结构】【链表】删除排序链表中的重复元素

    链表

    链表

    当涉及到数据结构时，链表是一种常见且重要的数据结构。链表由一系列节点组成，每个节点包含数据和指向下一个节点的引用。相比于数组，链表的大小可以动态地增长或缩小，因为每个节点只需要存储自己的数据和指向下一个节点的引用。
    在这里插入图片描述

    单向链表

    首先，我们需要定义一个表示链表节点的类。节点类应该包含一个数据字段和一个指向下一个节点的引用字段。可以使用泛型来使节点类更加通用。

    class ListNode<T> {
    T data;
    ListNode<T> next;

    public ListNode(T data) {
        this.data = data;
        this.next = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    接下来，我们可以创建一个链表类，它包含对链表进行操作的方法，如插入节点、删除节点和遍历链表等。

    class LinkedList<T> {
    private ListNode<T> head;

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

    // 在链表头部插入节点
    public void insertAtHead(T data) {
        ListNode<T> newNode = new ListNode<>(data);
        newNode.next = head;
        head = newNode;
    }

    // 在链表尾部插入节点
    public void insertAtTail(T data) {
        ListNode<T> newNode = new ListNode<>(data);
        if (head == null) {
            head = newNode;
        } else {
            ListNode<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 删除指定节点
    public void deleteNode(T data) {
        if (head == null) {
            return;
        }
        if (head.data.equals(data)) {
            head = head.next;
            return;
        }
        ListNode<T> current = head;
        while (current.next != null) {
            if (current.next.data.equals(data)) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 遍历链表并打印节点数据
    public void printList() {
        ListNode<T> current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    现在，我们可以使用链表类来创建链表对象，并进行插入、删除和遍历等操作。

    public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.insertAtHead(3);
        linkedList.insertAtHead(2);
        linkedList.insertAtHead(1);
        linkedList.insertAtTail(4);
        linkedList.printList(); // 输出: 1 2 3 4

        linkedList.deleteNode(2);
        linkedList.printList(); // 输出: 1 3 4
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    这就是一个简单的链表教程，它展示了如何使用Java语言来实现链表的基本操作。通过理解链表的结构和使用方法，你可以在编程中灵活地应用链表来解决各种问题。

    双向链表

    双向链表（Doubly Linked List）是一种链表的变体，每个节点除了包含数据和指向下一个节点的引用外，还包含指向前一个节点的引用。这使得双向链表可以在正向和反向两个方向上遍历。

    下面是一个用Java语言描述双向链表的简单教程：

    首先，我们需要定义一个表示双向链表节点的类。节点类应该包含一个数据字段，一个指向前一个节点的引用字段和一个指向后一个节点的引用字段。同样，可以使用泛型来使节点类更加通用。

    class DoublyListNode<T> {
    T data;
    DoublyListNode<T> prev;
    DoublyListNode<T> next;

    public DoublyListNode(T data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    接下来，我们可以创建一个双向链表类，它包含对双向链表进行操作的方法，如插入节点、删除节点和遍历链表等。

    class DoublyLinkedList<T> {
    private DoublyListNode<T> head;

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

    // 在链表头部插入节点
    public void insertAtHead(T data) {
        DoublyListNode<T> newNode = new DoublyListNode<>(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 在链表尾部插入节点
    public void insertAtTail(T data) {
        DoublyListNode<T> newNode = new DoublyListNode<>(data);
        if (head == null) {
            head = newNode;
        } else {
            DoublyListNode<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
            newNode.prev = current;
        }
    }

    // 删除指定节点
    public void deleteNode(T data) {
        if (head == null) {
            return;
        }
        if (head.data.equals(data)) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return;
        }
        DoublyListNode<T> current = head;
        while (current != null) {
            if (current.data.equals(data)) {
                current.prev.next = current.next;
                if (current.next != null) {
                    current.next.prev = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    // 遍历链表并打印节点数据
    public void printList() {
        DoublyListNode<T> current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    现在，我们可以使用双向链表类来创建双向链表对象，并进行插入、删除和遍历等操作。

    public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> doublyLinkedList = new DoublyLinkedList<>();
        doublyLinkedList.insertAtHead(3);
        doublyLinkedList.insertAtHead(2);
        doublyLinkedList.insertAtHead(1);
        doublyLinkedList.insertAtTail(4);
        doublyLinkedList.printList(); // 输出: 1 2 3 4

        doublyLinkedList.deleteNode(2);
        doublyLinkedList.printList(); // 输出: 1 3 4
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    这就是一个简单的双向链表，它展示了如何使用Java语言来实现双向链表的基本操作。通过理解双向链表的结构和使用方法，你可以在编程中灵活地应用双向链表来解决各种问题。

    题目

    在这里插入图片描述
    ListNode

    public class ListNode {

    int val;
    ListNode next;
    ListNode prev;

    public ListNode() {
    }

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

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

    ListNode(int x, ListNode next, ListNode prev) {
        val = x;
        this.next = next;
        this.prev = prev;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    代码

    在这里插入图片描述

    public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode dummy = new ListNode(0, head);
    ListNode cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        if (cur.next.val == cur.next.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }

    return dummy.next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    现在要把所有的重复元素全部删除要怎么做？

    public ListNode deleteDuplicatesAll(ListNode head) {
    if (head == null) {
        return null;
    }

    ListNode dummy = new ListNode(0, head);
    ListNode cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        if (cur.next.val == cur.next.next.val) {
            cur.next = cur.next.next;
            int x = cur.next.val;
            while (cur.next != null && cur.next.val == x) {
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next;
        }
    }

    return dummy.next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    这段代码实现了删除链表中所有重复的节点。下面是对代码的解析和题解：

    1. 首先，检查链表头节点是否为空，如果为空，则直接返回空链表。
    2. 创建一个虚拟节点 dummy，将其指向头节点 head。这样做是为了方便处理头节点可能被删除的情况。
    3. 使用指针 cur 来遍历链表，初始时指向虚拟节点 dummy。
    4. 在循环中，检查当前节点 cur 的下一个节点 cur.next 和下下个节点 cur.next.next 是否存在。如果两个节点的值相等，说明存在重复节点。
    5. 将 cur.next 指向下下个节点 cur.next.next，跳过重复节点。
    6. 使用变量 x 记录被删除的重复节点的值，然后继续循环，删除链表中所有与 x 相等的节点。
    7. 如果 cur.next 和 cur.next.next 的值不相等，说明当前节点没有重复，将 cur 移动到下一个节点。
    8. 循环结束后，返回虚拟节点 dummy 的下一个节点作为新的链表头节点。

    这段代码的时间复杂度为 O ( n ) O(n) O(n)，其中 n n n 是链表的长度，因为我们只遍历了一次链表。空间复杂度为 O ( 1 ) O(1) O(1)，只使用了常数级别的额外空间。
    可以有效地删除链表中所有重复的节点，保留不重复的节点。

  • 相关阅读:
    拿到PMP证书后你必须做的事情
    idea插件开发-UAST
    阿里云大数据实战记录2：调度实例跑完数据表为空？
    【Autosar RTM】
    贝叶斯分位数回归、lasso和自适应lasso贝叶斯分位数回归分析免疫球蛋白、前列腺癌数据...
    Android 启动优化系列 —— 系统启动流程
    Java之spring新手教程(包教包会)
    基于HTML仿oppo手机商城电商项目的设计与实现6个页面
    获取注解信息
    SqlServer中去除字段空格及特殊空格/回车/换行等
  • 原文地址：https://blog.csdn.net/yh4494/article/details/137905374