DS单链表—删除重复元素
时间: 2024-09-15 13:08:09 浏览: 40
DS(Data Structure)单链表是一种线性数据结构,其中每个节点包含数据和指向下一个节点的指针。删除重复元素是指从给定的单链表中移除所有相等的值,保留每个值第一次出现的位置。
一种常见的方法是遍历链表,使用两个指针,一个普通地向前移动(快指针),另一个检查当前节点是否等于前一个节点,如果相等则将前一个节点的next指向当前节点的下一个节点,跳过重复部分(慢指针)。当遇到不重复的节点时,快指针继续前进。
伪代码如下:
```python
def deleteDuplicates(head):
if not head or not head.next:
return head
current = head
while current and current.next:
if current.data == current.next.data:
current.next = current.next.next
else:
current = current.next
return head
```
相关问题
DS单链表 存储结构与操作
DS单链表是一种常见的数据结构,用于存储和操作数据。它由一系列的节点组成,每个节点包含两个部分:数据域和指针域。数据域用于存储数据,指针域用于指向下一个节点。通过指针域的连接,可以形成一个链式结构。
对于DS单链表的操作,包括以下几个常见的操作:
1. 初始化链表:创建一个空链表,将头节点的指针指向NULL。
2. 插入节点:在链表的指定位置插入一个新节点,需要修改前一个节点的指针域和新节点的指针域。
3. 删除节点:删除链表中的指定节点,需要修改前一个节点的指针域和被删除节点的指针域。
4. 查找节点:按照给定的关键字或位置查找链表中的节点。
5. 遍历链表:按照指针域的连接顺序,依次访问链表中的每个节点。
DS单链表--存储结构与操作
DS单链表是一种线性数据结构,它由若干个节点组成,每个节点包括数据域和指针域,其中数据域用于存储数据,指针域用于指向下一个节点。DS单链表的存储结构如下:
```
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
其中,val表示节点存储的数据,next表示指向下一个节点的指针。
DS单链表的基本操作包括:创建、插入、删除、查找、遍历等。
1. 创建
创建DS单链表的方法有多种,例如头插法、尾插法等。其中,头插法的实现代码如下:
```
ListNode* createList(int arr[], int n) {
ListNode *head = NULL;
for (int i = 0; i < n; i++) {
ListNode *node = (ListNode*)malloc(sizeof(ListNode));
node->val = arr[i];
node->next = head;
head = node;
}
return head;
}
```
2. 插入
DS单链表的插入操作包括在指定位置插入节点和在末尾插入节点。其中,指定位置插入节点的实现代码如下:
```
void insert(ListNode *head, int val, int pos) {
ListNode *node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
ListNode *p = head;
for (int i = 1; i < pos && p != NULL; i++) {
p = p->next;
}
if (p == NULL) {
return;
}
node->next = p->next;
p->next = node;
}
```
3. 删除
DS单链表的删除操作包括删除指定位置的节点和删除指定值的节点。其中,删除指定位置的节点的实现代码如下:
```
void delete(ListNode *head, int pos) {
ListNode *p = head;
ListNode *q = NULL;
for (int i = 1; i < pos && p != NULL; i++) {
q = p;
p = p->next;
}
if (p == NULL) {
return;
}
if (q == NULL) {
head = head->next;
} else {
q->next = p->next;
}
free(p);
}
```
4. 查找
DS单链表的查找操作包括查找指定位置的节点和查找指定值的节点。其中,查找指定值的节点的实现代码如下:
```
ListNode* find(ListNode *head, int val) {
ListNode *p = head;
while (p != NULL) {
if (p->val == val) {
return p;
}
p = p->next;
}
return NULL;
}
```
5. 遍历
DS单链表的遍历操作包括正向遍历和反向遍历。其中,正向遍历的实现代码如下:
```
void traverse(ListNode *head) {
ListNode *p = head;
while (p != NULL) {
printf("%d ", p->val);
p = p->next;
}
}
```
以上就是DS单链表的存储结构与操作的介绍。