15
- 跟上一题差不多，只是不让存入新链表，思路还是一样的
- 我们只需要把A链表当作一个新链表，记录A链表的尾结点，然后每次尾插就可以了
- 这就是归并的思想，同步遍历两个链表
- 时间复杂度O(n)，空间复杂度O(1)
void getSame(LinkList A, LinkList B) { // 1.创建工作指针 LNode *pa = A->next, *pb = B->next, *tail = A; // 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.找到相等结点就尾插 tail->next = pa; tail = pa; pa = pa->next; pb = pb->next; } } } 复制代码
- 题中没有要求释放结点，如果要求的话需要在每个
if分支释放多余结点 - 最后收尾，将结果链表尾指针置为NULL
- 通常清空会剩下一个非空链表，释放剩余空间
- 最后释放B链表头结点
void getSame2(LinkList A, LinkList B) { LNode *pa = A->next, *pb = B->next, *tail = A, *del; while (pa != NULL && pb != NULL) { if (pa->data < pb->data) { del = pa; pa = pa->next; free(del); } else if (pa->data > pb->data) { del = pb; pb = pb->next; free(del); } else { tail->next = pa; tail = pa; pa = pa->next; del = pb; pb = pb->next; free(del); } } // 收尾 tail->next = NULL; // 释放剩余空间 while (pa != NULL) { del = pa; pa = pa->next; free(del); } while (pb != NULL) { del = pb; pb = pb->next; free(del); } free(B); } 复制代码
16
- 判断连续子序列的链表版，其实跟字符串是一样的
- 两个链表都从第一个结点开始比较，如果不同
- 则A链表从下一个结点开始，B链表从头开始
- B链表能匹配到表尾表示匹配成功
- 时间复杂度O(n2)，空间复杂度O(1)
bool isSubseq(LinkList A, LinkList B) { // 1.创建工作指针，p记录每趟比较中的开始结点 LNode *pa = A->next, *pb = B->next, *p = A->next; // 2.遍历 while (pa != NULL && pb != NULL) { if (pa->data == pb->data) { pa = pa->next; pb = pb->next; } else { p = p->next; pa = p; // 重新开始一趟比较 pb = B->next; } } if (pb == NULL) return true; // 3.如果pb都能匹配上，证明是A的子序列 return false; }
