12
- 有序表，直接循环扫描
- 判断是否相等，相等直接删除，释放空间
- 不等就下一个
- 时间复杂度O(n)，空间复杂度O(1)
void delSame(LinkList &L) { LNode *p = L->next, *del; while (p->next != NULL) { if (p->data == p->next->data) { del = p->next; p->next = del->next; free(del); } else { p = p->next; } } } 复制代码
13
- 经典合并链表！不过是两个递增合并为一个递减，头插即可
- 因为哪哪都要用到头插，我们可以把它抽离成一个单独的函数使用
- 遍历完后，肯定有一个链表有剩余元素，我们可以通过
if (pa == NULL) pa = pb;节省步骤 - 时间复杂度O(n)，空间复杂度O(n)
// 头插 void headInsert(LinkList &L, int num) { LNode* node = (LNode *)malloc(sizeof(LNode)); node->data = num; node->next = L->next; L->next = node; } LinkList mergeList(LinkList A, LinkList B) { // 1.创建一个新链表 LNode* L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; // 2.遍历插入 LNode *pa = A->next, *pb = B->next, *q; while (pa != NULL && pb != NULL) { if (pa->data < pb->data) { headInsert(L, pa->data); pa = pa->next; } else { headInsert(L, pb->data); pb = pb->next; } } // 3.处理剩余元素 if (pa == NULL) pa = pb; while (pa != NULL) { headInsert(L, pa->data); pa = pa->next; } return L; } 复制代码
14
- 创建一个新链表C，找到公共元素尾插进去，每次只记录尾结点
- 同时遍历A，B找出结点值相等的元素
- 时间复杂度O(n)，空间复杂度O(1)
LinkList getSame(LinkList A, LinkList B) { // 1.创建链表和指针 LNode* C = (LinkList)malloc(sizeof(LNode)); C->next = NULL; LNode *tail = C, *pa = A->next, *pb = B->next, *node; // 2.同步遍历 while (pa != NULL && pb != NULL) { if (pa->data < pb->data) { pa = pa->next; } else if (pa->data > pb->data) { pb = pb->next; } else { // 3.相等就尾插进新链表 node = (LNode*)malloc(sizeof(LNode)); node->data = pa->data; tail->next = node; tail = node; // 4.继续向后扫描 pa = pa->next; pb = pb->next; } } return C; }
