设计在单链表中删除值相同的多余结点的算法
时间: 2023-04-18 22:01:21 浏览: 109
算法思路:
1. 定义一个指针current, 从链表的头结点开始遍历链表
2. 定义一个指针runner, 从current的下一个结点开始遍历
3. 如果runner所指向的结点的值和current所指向的结点的值相同,则删除runner所指向的结点
4. 如果runner所指向的结点的值和current所指向的结点的值不相同,则current移动到runner所指向的结点
5. 重复步骤3和4,直到runner到达链表的末尾
6. 返回处理后的链表
代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def remove_duplicate(head):
current = head
while current:
runner = current
while runner.next:
if runner.next.val == current.val:
runner.next = runner.next.next
else:
runner = runner.next
current = current.next
return head
```
注意: 上述算法只适用于单链表,对于双链表或循环链表需要做修改.
相关问题
设单链表以非递减有序排列,设计算法实现在单链表中删除值相同的多余结点
算法步骤如下:
1. 定义两个指针p和q,p指向当前结点,q指向下一个结点。
2. 如果p结点的值等于q结点的值,则将q结点从链表中删除,并释放其内存空间。
3. 如果p结点的值不等于q结点的值,则将p指针后移一位,继续比较下一个结点。
4. 重复步骤2和3,直到p指针指向链表的最后一个结点。
5. 返回删除多余结点后的链表。
代码实现如下:
```
void removeDuplicates(ListNode* head) {
ListNode* p = head;
while (p != NULL && p->next != NULL) {
if (p->val == p->next->val) {
ListNode* q = p->next;
p->next = q->next;
delete q;
} else {
p = p->next;
}
}
}
```
设计一个算法,在非递减有序的带头结点的单链表中删除值相同的多余结点。
算法步骤如下:
1. 定义两个指针p和q,p指向头结点,q指向第一个非头结点。
2. 循环遍历链表,如果p的值等于q的值,则删除q结点,否则p和q同时后移一个结点。
3. 循环结束后,返回头结点即可。
代码实现如下:
```
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = p->next;
q = q->next;
}
}
return head;
}
```