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

题目要求

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

示例解释

示例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]

关键点

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

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

#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 -> 1ListNode *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;
}