已知一个元素值递增有序的单链表l(允许出现值重复的结点),设计算法删除值重复的结点。
时间: 2023-04-27 18:00:39 浏览: 128
算法步骤如下:
1. 定义两个指针p和q,分别指向链表的头结点和第二个结点。
2. 遍历链表,如果p指向的结点的值等于q指向的结点的值,则删除q指向的结点,并将q指向下一个结点。
3. 如果p指向的结点的值不等于q指向的结点的值,则将p和q都向后移动一个结点。
4. 重复步骤2和步骤3,直到q指向链表的最后一个结点。
5. 返回链表的头结点。
算法的时间复杂度为O(n),其中n为链表的长度。
相关问题
已知一个递增有序的不带头结点的单链表,设计算法从该链表删除与给定值相等的所有元素
可以回答这个问题。算法如下:
1. 定义两个指针,分别指向当前节点和前一个节点。
2. 遍历链表,如果当前节点的值等于给定值,则删除该节点。
3. 如果当前节点的值不等于给定值,则将前一个节点指向当前节点。
4. 遍历完整个链表后,返回链表头节点。
具体实现可以参考以下代码:
struct ListNode* deleteNode(struct ListNode* head, int val) {
struct ListNode *prev = NULL, *curr = head;
while (curr != NULL) {
if (curr->val == val) {
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
curr = prev == NULL ? head : prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return head;
}
已知带头结点的动态单链表是按整数值递增进行排列,写一算法插入x
以下是插入x的算法:
1. 创建一个新的节点,将x存储在其中。
2. 找到第一个大于x的节点p和p的前驱节点q。
3. 将新节点插入到q和p之间。
具体实现代码如下:
void insert(Node* head, int x) {
Node* p = head->next;
Node* q = head;
while (p != NULL && p->data < x) {
q = p;
p = p->next;
}
Node* newNode = new Node(x);
newNode->next = p;
q->next = newNode;
}