2.3.7, 8
- 首先要理解公共结点的含义，当两个链表从某一个结点开始，指针都指向同一个结点，那么这个结点就是公共结点，整个形状呈现一个Y型
- 暴力解法，双重循环，遍历第一个链表的结点的同时遍历第二个链表所有的结点，找到相同点
- 时间复杂度O(n2)，或者说O(len1×len2)，空间复杂度O(1)
LNode* findCommon(LinkList A, LinkList B) { LNode *pa = A->next, *pb = B->next; while (pa != NULL) { while (pb != NULL) { if (pa == pb) return pa; pb = pb->next; } pa = pa->next; pb = B->next; // 重置指针 } return NULL; // 没找到返回NULL } 复制代码
- 如果两个链表有公共结点，那么在公共结点后的所有结点都是重合的，我们只需要将链表的长度整成相同的，然后向后找第一个相同点即可
- 先分别获得两个链表的长度，做差，将其长度置为相同
- 同步遍历，找到相同结点即可
- 时间复杂度O(n)，空间复杂度O(1)
int getLen(LinkList L) { int len = 0; while (L->next != NULL) { L = L->next; len++; } return len; } LNode* findCommon2(LinkList A, LinkList B) { // 1.计算A, B的长度 int lenA = getLen(A), lenB = getLen(B); // 2.让A, B的长度差距为0 if (lenA > lenB) { for (int i = 0; i < lenA - lenB; i++) A = A->next; } else { for (int i = 0; i < lenB - lenA; i++) B = B->next; } // 3.开始比较 while (A != NULL) { if (A == B) return A; A = A->next; B = B->next; } // 4.没找到返回NULL return NULL; } 复制代码
2.3.7, 9
- 按照递增次序输出结点，然后删除
- 其实就是每次找到链表的最小值元素，输出后删除
- 删除一个元素需要记录它的前驱结点
- 时间复杂度O(n2)，空间复杂度O(1)
- 如果可以用数组，就把元素拿出来放到数组里排序，时间复杂度O(nlog2n)，空间复杂度O(n)
void delMin(LinkList &L) { // 1.只剩一个头结点时停止 while (L->next != NULL) { LNode *minpre = L, *p = L->next; // 2.找到最小值，记录其前缀 while (p->next != NULL) { if (p->next->data < minpre->next->data) minpre = p; p = p->next; } // 3.输出并释放最小值结点 cout << minpre->next->data << ' '; LNode *del = minpre->next; minpre->next = del->next; free(del); } // 4.释放头结点 free(L); }
