Leetcode 面试题 02.01. 移除重复节点

题目描述

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

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

示例2:

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

提示：

1. 链表长度在[0, 20000]范围内。
2. 链表元素在[0, 20000]范围内。

 双指针方法，定义两个指针cur与p来逐个遍历链表，cur元素依次和p比较，直到p为NULL，cur向后移动一个。

完整代码：

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        // 如果链表为空，直接返回 NULL
        if (head == NULL) {
            return NULL;
        }
        
        // 当前遍历到的节点
        ListNode *cur = head;
        
        // 遍历链表，直到当前节点的下一个节点为空
        while (cur != NULL && cur->next != NULL) {
            // 内部遍历指针，从当前节点开始检查重复
            ListNode *p = cur;
            
            // 检查下一个节点是否与当前节点的值相同
            while (p->next != NULL) {
                if (p->next->val == cur->val) {
                    // 如果下一个节点的值与当前节点相同，删除下一个节点
                    ListNode *tmp = p->next;
                    p->next = p->next->next;
                    delete tmp; // 删除节点释放内存
                } else {
                    // 如果下一个节点的值不同，则移动指针到下一个节点
                    p = p->next;
                }
            }
            
            // 移动当前指针到下一个节点
            cur = cur->next;
        }
        
        // 返回去重后的链表头节点
        return head;
    }
};