当前位置：首页 > article >正文

数据结构与算法——Java实现 11.习题——有序链表去重

article 2024/9/23 11:26:38

目录

82. 删除排序链表中的重复元素 II

方法1

方法2

要知道，每一颗钻石在被发现前，都要经受埋藏尘埃的寂寞时光

—— 24.9.23

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

注意：重复元素一个不留

方法1

递归函数负责返回：从当前节点开始，完成去重的链表

1.若当前节点与next重复，一直找到下一个不重复的节点，以它的返回结果为准

2.若当前节点与next不重复，返回当前节点，同时更新next节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if(head.val == head.next.val){
            ListNode x = head.next.next;
            while(x != null && x.val == head.val){
                x = x.next;
            }
            // 与p取值不同的节点
            return deleteDuplicates(x);
        }else{
            head.next = deleteDuplicates(head.next);
            return head;
        }
    }
}

方法2

非递归、一次遍历实现

建立三个指针，指针1指向哨兵节点，指针2和指针3指向第一、二个节点，如果指针2和指针3指向的节点相同，则将他们删去，如果指针2和指针3指向的元素不相等，则将指针2、3都往后移动一位，知道指针3指向为null时，遍历结束

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = new ListNode(-1, head);
        ListNode node = s;
        while (node.next != null && node.next.next != null){
            if (node.next.val == node.next.next.val){
                int x = node.next.val;
                while(node.next != null && node.next.val == x){
                    node.next = node.next.next;
                }
            }else{
                node = node.next;
            }
        }
        return s.next;
    }
}