极客教程C++程序 给定一个单向链表的交替拆分-1
编写一个名为AlternatingSplit()的函数，它接收一个列表，并将其节点分成两个更小的列表’a’和’b’。子列表应该由原始列表中的交替元素组成。因此，如果原始列表是0->1->0->1->0->1，则一个子列表应该是0-> 0->0，另一个子列表应该是1->1->1。
方法1(简单)：
最简单的方法是遍历源列表，并从源列表中获取节点，然后交替将它们放在’a’和’b’的前面(或开始)。唯一奇怪的部分是，节点将以在源列表中发生的相反顺序排列。方法2通过跟踪子列表中的最后一个节点，在末尾插入节点。
/* C++ Program to alternatively split
a linked list into two halves */
#include <bits/stdc++.h>
using namespace std;
// Link list node
class Node
{
public:
int data;
Node* next;
};
/* Pull off the front node of
the source and put it in dest */
void MoveNode(Node** destRef,
Node** sourceRef) ;
/* Given the source list, split its nodes
into two shorter lists. If we number the
elements 0, 1, 2, ... then all the even
elements should go in the first list, and
all the odd elements in the second. The
elements in the new lists may be in any order. */
void AlternatingSplit(Node* source,
Node** aRef,
Node** bRef)
{
/* Split the nodes of source
to these 'a' and 'b' lists */
Node* a = NULL;
Node* b = NULL;
Node* current = source;
while (current != NULL)
{
// Move a node to list 'a'
MoveNode(&a, &t);
if (current != NULL)
{
// Move a node to list 'b'
MoveNode(&b, &t);
}
}
*aRef = a;
*bRef = b;
}
/* Take the node from the front of
the source, and move it to the front
of the dest. It is an error to call
this with the source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
void MoveNode(Node** destRef,
Node** sourceRef)
{
// The front source node
Node* newNode = *sourceRef;
assert(newNode != NULL);
// Advance the source pointer
*sourceRef = newNode->next;
// Link the old dest off the
// new node
newNode->next = *destRef;
// Move dest to point to the
// new node
*destRef = newNode;
}
// Utility Functions
/* Function to insert a node at
the beginning of the linked list */
void push(Node** head_ref,
int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list of the
// new node
new_node->next = (*head_ref);
// Move the head to point to the
// new node
(*head_ref) = new_node;
}
/* Function to print nodes
in a given linked list */
void printList(Node *node)
{
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
Node* a = NULL;
Node* b = NULL;
/* Let us create a sorted linked list
to test the functions
Created linked list will be
0->1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
push(&head, 0);
cout << "Original linked List: ";
printList(head);
// Remove duplicates from linked list
AlternatingSplit(head, &a, &b);
cout << "Resultant Linked List 'a' : ";
printList(a);
cout << "Resultant Linked List 'b' : ";
printList(b);
return 0;
}
// This code is contributed by rathbhupendra```
输出:
原始链表: 0 1 2 3 4 5
结果链表 'a' : 4 2 0
结果链表 'b' : 5 3 1
时间复杂度：O(n)， 其中n是给定链接列表中的节点数。
辅助空间：O(1)
方法2（使用虚拟节点）：
这是一种替代方法，该方法按照与源列表相同的顺序构建子列表。代码在构建“a”和“b”列表时使用临时虚拟头节点。每个子列表都有一个“tail”指针，指向其当前的最后一个节点 – 这样可以轻松地将新节点附加到每个列表的末尾。虚拟节点最初为尾指针提供了一些指向的对象。在这种情况下，虚拟节点效率很高，因为它们是临时分配的，分配在堆栈中。也可以使用本地的“引用指针”（它们始终指向列表中的最后一个指针而不是最后一个节点），以避免使用虚拟节点。
void AlternatingSplit(Node* source,
Node** aRef,
Node** bRef)
{
Node aDummy;
// 指向'a'中的最后一个节点
Node* aTail = &aDummy
Node bDummy;
// 指向'b'中的最后一个节点
Node* bTail = &bDummy
Node* current = source;
aDummy.next = NULL;
bDummy.next = NULL;
while (current != NULL)
{
// 添加到'a'中的末尾
MoveNode(&(aTail->next), &t);
// 推进'a'的末尾
aTail = aTail->next;
if (current != NULL)
{
MoveNode(&(bTail->next), ¤t);
bTail = bTail->next;
}
}
*aRef = aDummy.next;
*bRef = bDummy.next;
}
// 此代码由rathbhupendra提供```
时间复杂度： O（n），其中n是给定链表中的节点数。
空间复杂度： O（n），因为该函数创建了2个新的链表。