创建一个带头结点的单链表hc,设计算法lksplit将该链表拆分为两个单链表ha和hb,其中,ha各节点依次为hc中的奇数号结点,hb各节点依次为hc中的偶数号结点。
时间: 2023-04-29 17:01:40 浏览: 154
3-2 试编写一个算法,在带表头结点的单链表中寻找第i个结点.doc
算法lksplit的实现步骤如下:
1. 定义指针p和q,分别指向链表hc的头结点和第一个奇数号结点。
2. 定义指针r和s,分别指向链表ha和hb的头结点。
3. 使用while循环遍历链表hc,每次循环p指向下一个结点,q指向下一个奇数号结点。
4. 如果q不为空,则将q插入到链表ha中,同时r指向下一个结点。
5. 如果p不为空,则将p插入到链表hb中,同时s指向下一个结点。
6. 循环结束后,将链表ha和hb的尾结点指向空。
7. 返回链表ha和hb。
算法lksplit的时间复杂度为O(n),其中n为链表hc的长度。
阅读全文