C语言刷题 LeetCode 删除单链表的重复节点 双指针法

题目要求

1. 链表结构：题目中提到的是未排序的链表，链表是由一系列节点组成的，每个节点包含一个值（数据）和一个指向下一个节点的指针。
2. 去重：我们需要遍历链表，删除所有重复的节点，只保留每个值第一次出现的节点。
3. 输出结果：输出去重后的链表。

示例解释

• 示例1：

  • 输入: [1,2,3,3,2,1]
    • 链表结构为: 1 -> 2 -> 3 -> 3 -> 2 -> 1
    • 处理后: 去掉重复的 3 和 2 之后，结果是 1 -> 2 -> 3
  • 输出: [1, 2, 3]

• 示例2：

  • 输入: [1,1,1,1,2]
    • 链表结构为: 1 -> 1 -> 1 -> 1 -> 2
    • 处理后: 去掉重复的 1，结果是 1 -> 2
  • 输出: [1, 2]

关键点

1. 链表的遍历：我们需要遍历整个链表来找出并删除重复的节点。
2. 存储已出现的值：我们需要一种方式来跟踪已经出现的节点值，以便知道哪些需要删除。这个可以使用额外的存储结构（如哈希表）来实现。
3. 双指针技巧：在进阶要求中，不能使用临时缓冲区，这时可以用双指针的方式直接在链表中进行比较和删除。

不使用临时缓冲区（双指针法）

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 移除重复节点的函数
ListNode* removeDuplicates(ListNode* head) {
    if (!head) return NULL;

    ListNode *current = head;

    while (current) {
        ListNode *runner = current;
        // 检查当前节点后面的节点
        while (runner->next) {
            if (runner->next->val == current->val) {
                // 找到重复节点，删除它
                ListNode *temp = runner->next;
                runner->next = runner->next->next; // 跳过重复节点
                free(temp); // 释放重复节点的内存
            } else {
                runner = runner->next; // 否则继续前进
            }
        }
        current = current->next; // 移动到下一个节点
    }

    return head;
}

// 辅助函数: 创建新节点
ListNode* createNode(int val) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 辅助函数: 打印链表
void printList(ListNode *head) {
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

// 示例用法
int main() {
    // 构建链表: 1 -> 2 -> 3 -> 3 -> 2 -> 1
    ListNode *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(3);
    head->next->next->next->next = createNode(2);
    head->next->next->next->next->next = createNode(1);

    printf("Original list: ");
    printList(head);

    head = removeDuplicates(head);

    printf("List after removing duplicates: ");
    printList(head);

    // 释放链表内存
    while (head) {
        ListNode *temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}