题目
设有一个带头结点的单链表 $L = (a_1, b_1, a_2, b_2, …, a_n, b_n)$，请设计一个算法将链表拆分为两个带头结点的单链表 $L_1 = (a_1, a_2, …, a_n)$ 和 $L_2 = (b_n, b_{n-1}, …, b_1)$，要求 $L_1$ 保持原顺序，$L_2$ 为逆序。
[答案]
void splitList(LinkList L, LinkList *L1, LinkList *L2) {
*L1 = L;
*L2 = (LinkList)malloc(sizeof(LNode));
(*L2)->next = NULL;
LNode *p = (*L1)->next; // 当前指针
while (p != NULL && p->next != NULL) {
// 保存a结点
LNode *a = p;
p = p->next;
// 保存b结点并头插到L2
LNode *b = p->next;
p->next = b->next;
b->next = (*L2)->next;
(*L2)->next = b;
p = a->next;
}
}
[解析]
- 使用一个指针遍历原链表
- 每隔一个结点取出，采用头插法插入到新链表 $L_2$
- 头插法自然实现了逆序