C++程序给定一个单向链表的交替拆分-第1集

链表是数据结构中常见的一种。它是由许多节点组成的，每个节点包含一个数据元素和一个指针指向下一个节点。单向链表的每个节点只有一个指针指向下一个节点，不能回溯到前面的节点。本文将讲述如何给定一个单向链表完成交替拆分的算法以及C++代码实现。

假设给定一个单向链表如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createList(vector<int> nums) {
    ListNode *dummy = new ListNode(0);
    ListNode *cur = dummy;
    for(int i = 0; i < nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return dummy->next;
}

以上代码建立了一个链表创建函数createList，它根据输入的数组实现链表的建立。进一步构建一个输入数组为{1, 2, 3, 4, 5, 6}的链表：

ListNode* head = createList({1, 2, 3, 4, 5, 6});

其中，变量head指向了链表的头节点。

交替拆分的思路

本文所述的交替拆分指定的链表按顺序交替取出其中的节点构成两个新的链表。例如，原链表为1->2->3->4->5，则交替拆分后新链表为1->3->5和2->4，每个链表保持原始的顺序。

根据这个思路，我们可以定义两个空链表head1和head2，然后将原始链表中的奇数节点添加到head1中，将偶数节点添加到head2中。

ListNode* splitList(ListNode* head) {
    ListNode *head1 = new ListNode(0);
    ListNode *cur1 = head1;
    ListNode *head2 = new ListNode(0);
    ListNode *cur2 = head2;
    int i = 1;
    while(head) {
        if(i % 2 == 1) {
            cur1->next = head;
            cur1 = cur1->next;       
        }
        else {
            cur2->next = head;
            cur2 = cur2->next;              
        }
        head = head->next;
        i++;
    }
    cur1->next = nullptr;
    cur2->next = nullptr;
    return head1->next;
}

在代码中，变量cur1指向head1链表的最后一个节点，变量cur2指向head2链表的最后一个节点。变量i表示迭代次数，通过i的奇偶性来将节点添加到head1或head2。在最后，将head1和head2的最后一个节点指向nullptr，最后返回head1的下一个节点，即完整的链表。