假设循环链表L1,其遍历结果是x_1,x_2,x_3,〖…,x〗_n,请将该循环链表拆为两个循环单链表L1和L2,使得L1中含有原L1表中的序号为奇数的结点,且遍历结果为x_1,x_3…,L2中含有原L表中为偶数的结点且遍历结果为〖…x〗_4,x_2,尽量高效。
时间: 2023-03-25 20:03:53 浏览: 117
将一个结点值自然数的单链表拆分为两个单链表,原表中保留值为偶数的结点,而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表
可以使用两个指针p1和p2,分别指向L1的第一个结点和第二个结点。然后,p1每次向后移动两个结点,p2每次向后移动一个结点,直到p2指向L1的最后一个结点。这样,p1指向的结点就是L1中序号为奇数的结点,p2指向的结点就是L1中序号为偶数的结点。接着,将p2的下一个结点指向p1,这样就将L1拆分成了两个循环单链表L1和L2。最后,将L2的头结点指向p2的下一个结点即可。这种方法的时间复杂度为O(n),空间复杂度为O(1)。
阅读全文