已知一个递增有序的不带头结点的单链表,设计算法从该链表删除与给定值相等的所有元素
时间: 2023-03-26 16:00:39 浏览: 51
可以回答这个问题。算法如下:
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;
}
相关问题
已知一个元素值递增有序的单链表l(允许出现值重复的结点),设计算法删除值重复的结点。
算法步骤如下:
1. 定义两个指针p和q,分别指向链表的头结点和第二个结点。
2. 遍历链表,如果p指向的结点的值等于q指向的结点的值,则删除q指向的结点,并将q指向下一个结点。
3. 如果p指向的结点的值不等于q指向的结点的值,则将p和q都向后移动一个结点。
4. 重复步骤2和步骤3,直到q指向链表的最后一个结点。
5. 返回链表的头结点。
算法的时间复杂度为O(n),其中n为链表的长度。
有一个带头结点的双链表l,设计一个算法将其所有元素递增有序排列
以下是一个将带头结点的双链表所有元素递增有序排列的算法:
1. 将双链表的所有元素复制到一个数组中。
2. 对数组进行递增排序。
3. 将排序后的数组元素复制回双链表。
代码示例:
```python
def sort_double_linked_list(l):
# 复制链表元素到数组
arr = []
cur = l.next
while cur:
arr.append(cur.val)
cur = cur.next
# 对数组进行递增排序
arr.sort()
# 将排序后的数组元素复制回链表
cur = l.next
i = 0
while cur:
cur.val = arr[i]
cur = cur.next
i += 1
# 调用示例
sort_double_linked_list(l)
```