❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)

题目

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

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

Related Topics

链表

👍 1115

👎 0

思路

• 快慢指针法
• 其实这个和数组那个去重思路一模一样

解答

//给定一个已排序的链表的头
// head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,1,2]
//输出：[1,2]
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,1,2,3,3]
//输出：[1,2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围 [0, 300] 内 
// -100 <= Node.val <= 100 
// 题目数据保证链表已经按升序 排列 
// 
//
// Related Topics 链表 👍 1115 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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) return null;

        ListNode dummy = new ListNode(); // 创建一个哑节点作为新链表的头
        dummy.next = head;
        ListNode slow = dummy, fast = head;

        while (fast != null) {
            if (fast.next == null || fast.val != fast.next.val) {
                // 当fast指向的元素不重复时，将其连接到slow之后，并将slow向前移动
                slow.next = fast;
                slow = slow.next;
            }
            fast = fast.next; // fast继续向前移动
        }

        // 将slow之后的元素删除，确保链表在此之后没有其他的元素
        slow.next = null;

        return dummy.next; // 返回新链表的头（跳过哑节点）
    }
}
//leetcode submit region end(Prohibit modification and deletion)