目录

问题描述

示例1

示例2

解题思路

代码实现

代码解析

总结

---

问题描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→21→1→2,返回1→21→2.
给出的链表为1→1→2→3→31→1→2→3→3,返回1→2→31→2→3.

数据范围：链表长度满足 0≤n≤1000≤n≤100，链表中任意节点的值满足 ∣val∣≤100∣val∣≤100

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

示例1

输入：

{1,1,2}

返回值：

{1,2}

示例2

输入：

{}

返回值：

{}

解题思路

首先判断链表为空或只有一个节点的特殊情况，若满足条件直接返回头节点。然后，使用两个指针 left 和 right，分别指向当前链表的头节点和第二个节点。right 指针负责遍历链表，而 left 指针负责维护去重后的链表。当 left 和 right 指向的节点值不同，说明 right 指向的节点不重复，可以将 left 的 next 指向 right，并将 left 移动到 right。如果 left 和 right 指向的节点值相同，说明 right 指向的节点是重复的，直接跳过。最后，当遍历结束时，确保 left 的 next 为 nullptr，以防止尾部出现环。

代码实现

    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* left = head, *right = head->next;
        while(right)
        {
            if(left->val != right->val)
            {
                left->next = right;
                left = right;
            }
            right = right->next;
        }
        left->next = nullptr;
        return head;
    }

代码解析

1. 初始化和边界条件判断

if(head == nullptr || head->next == nullptr) return head;

2. 遍历链表

ListNode* left = head, *right = head->next;
while(right)
{
    if(left->val != right->val)
    {
        left->next = right;
        left = right;
    }
    right = right->next;
}

while(right) 循环遍历整个链表。当 right 不为空时，检查 left 和 right 指向的节点的值是否相同。如果值不同，说明 right 指向的节点不重复，可以保留。在这种情况下，将 left 的 next 指向 right，然后将 left 更新为 right，表示去重后的链表继续从 left 处开始。如果值相同，说明 right 指向的节点重复，直接跳过 right 节点，继续向后遍历。

3. 确保链表末尾的next为空

left->next = nullptr;

遍历结束后，left 指向去重后的链表的最后一个节点，需要将其 next 指针置为 nullptr，避免链表尾部出现环。

总结

代码实现了一个高效的链表去重算法，通过使用两个指针（left 和 right）遍历链表，比较相邻节点的值，删除重复元素。通过调整 left 的 next 指针来保留不重复的节点，最终确保链表无重复元素。