设计一个算法,在非递减有序的带头结点的单链表中删除值相同的多余结点。

算法步骤如下：

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;
}

相关问题

c语言程序设计 设单链表以非递减有序排序,设计算法实现在单链表中删去值相同的多余结点。

要实现删除已排序单链表中的重复元素，可以参考以下C语言代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, *LinkList;

void deleteDuplicatesSorted(LinkList& L) {
    LNode* p = L;
    while (p != NULL) {
        LNode* q = p->next;
        while (q != NULL && p->data == q->data) { // 如果当前节点与下一个节点数值相同
            LNode* temp = q; // 创建临时指针保存重复节点
            q = q->next; // 移动q到下一个不同值的节点
            free(temp); // 释放重复节点的空间
        }
        p = q; // 更新p指向下一个不同值的节点
    }
}

int main() {
    LinkList L = (LinkList)malloc(sizeof(LNode)); // 初始化链表
    // ... 填充已排序的链表 ...

    deleteDuplicatesSorted(L); // 删除重复节点

    // ... 链表遍历并打印 ...

    return 0;
}

这个算法通过双指针`p`和`q`遍历链表。当发现`p`指向的节点与`q`指向的节点值相等时，它会移动`q`并释放重复的节点。这样就可以保持链表的顺序，只保留每个唯一值。

用c++设计算法将两个递增有序的带头结点的单链表A、B合并为一个递减有序的带头结点的单链表，并要求算法的时间复杂度为两个表长之和的数量级。

算法思路如下：

1. 定义一个新的链表C，用于存储合并后的递减有序链表。
2. 定义三个指针pA、pB、pC分别指向链表A、B和C的头结点。
3. 分别比较pA和pB指向的结点的值，将其中较小的结点加入到链表C的头部，同时将pA或pB指向下一个结点。
4. 重复步骤3，直到链表A或B为空。
5. 将链表A或B中剩余的结点加入到链表C的头部。
6. 返回链表C的头结点。

时间复杂度分析：

在每次循环中，我们只移动了pA或pB指针中的一个，因此时间复杂度为O(m+n)，其中m和n分别是链表A和B的长度。因此，算法的时间复杂度为两个表长之和的数量级。

下面是C语言实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

ListNode* mergeLists(ListNode* A, ListNode* B) {
    ListNode* C = (ListNode*)malloc(sizeof(ListNode));
    C->next = NULL;
    ListNode* pA = A->next;
    ListNode* pB = B->next;
    while (pA != NULL && pB != NULL) {
        if (pA->val < pB->val) {
            ListNode* tmp = pA->next;
            pA->next = C->next;
            C->next = pA;
            pA = tmp;
        } else {
            ListNode* tmp = pB->next;
            pB->next = C->next;
            C->next = pB;
            pB = tmp;
        }
    }
    while (pA != NULL) {
        ListNode* tmp = pA->next;
        pA->next = C->next;
        C->next = pA;
        pA = tmp;
    }
    while (pB != NULL) {
        ListNode* tmp = pB->next;
        pB->next = C->next;
        C->next = pB;
        pB = tmp;
    }
    return C;
}

int main() {
    // 初始化链表A
    ListNode* A = (ListNode*)malloc(sizeof(ListNode));
    A->next = NULL;
    for (int i = 5; i >= 1; i--) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        node->next = A->next;
        A->next = node;
    }
    // 初始化链表B
    ListNode* B = (ListNode*)malloc(sizeof(ListNode));
    B->next = NULL;
    for (int i = 10; i >= 6; i--) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        node->next = B->next;
        B->next = node;
    }
    // 合并链表A和B
    ListNode* C = mergeLists(A, B);
    // 打印链表C
    ListNode* p = C->next;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
    return 0;
}