10
- 遍历，设一个变量查看奇偶，分别插入
- 保持相对顺序不变，采用尾插法
- 时间复杂度O(n)，空间复杂度O(1)
void splitList(LinkList L, LinkList &A, LinkList &B) { // 1.创建工作指针 LNode *p = L->next, *pa = A, *pb = B; int i = 1; while (p != NULL) { // 2.采用尾插法分别插入 if (i % 2 != 0) { pa->next = p; pa = p; } else { pb->next = p; pb = p; } p = p->next; // 继续处理 i++; } // 3.最后设为空 pa->next = NULL; pb->next = NULL; } 复制代码
- 当然你也可以不使用变量记录奇偶，一次循环处理两个就可以了
void splitList2(LinkList L, LinkList &A, LinkList &B) { // 1.创建工作指针 LNode *p = L->next, *pa = A, *pb = B; while (p != NULL) { // 2.采用尾插法分别插入 pa->next = p; pa = p; p = p->next; // 继续处理 if (p != NULL) { pb->next = p; pb = p; p = p->next; // 继续处理 } } // 3.最后设为空 pa->next = NULL; pb->next = NULL; } 复制代码
11
- 与上一题类似，不过在插入B时需要采用头插法使其逆序
- 头插时要注意记录后继元素，防止断链
- 就地算法，时间复杂度O(n)，空间复杂度O(1)
void splitList(LinkList L, LinkList &A, LinkList &B) { // 1.创建工作指针 LNode *p = L->next, *pa = A; int i = 1; while (p != NULL) { // 2.分别采用头插法和尾插法插入 if (i % 2 != 0) { pa->next = p; pa = p; p = p->next; } else { LNode *q = p->next; // 记录p的后继防止断链 p->next = B->next; B->next = p; p = q; } i++; } // 3.收尾 pa->next = NULL; } 复制代码
- 同上也可以不使用变量记录奇偶
void splitList2(LinkList L, LinkList &A, LinkList &B) { // 1.创建工作指针 LNode *p = L->next, *pa = A; while (p != NULL) { // 2.分别采用头插法和尾插法插入 pa->next = p; pa = p; p = p->next; if (p != NULL) { LNode *q = p->next; // 记录p的后继防止断链 p->next = B->next; B->next = p; p = q; } } // 3.收尾 pa->next = NULL; }
