WD-线性表拆分(2019-2020)
【问题描述】设C={a1,b1,a2,b2,...,an,bn}为一线性表，采用带头结点的单链表存放，编写一个就地算法，将其按奇偶位置拆分为两个线性表，使得：A={a1,a2,...,an}，B={b1,b2,...,bn}，其中C中至少含有一组有效数值。
【输入形式】a1 b1 a2 b2 ... an bn（数值用空格分隔，以回车作为结束标识）
【输出形式】a1 a2 ... an （分两行输出A，B，数值用空格分隔）

        b1 b2 ... bn
【样例输入】1 2 3 4 5 6 7 8
【样例输出】1 3 5 7

        2 4 6 8

#include<iostream>
#include <vector>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
};
typedef ListNode* LinkList;

void createListFromArray(LinkList &L,const vector<int>& arr){
    L = new ListNode{0,nullptr};
    ListNode* r = L;
    for(int val:arr){
        r->next = new ListNode{val,nullptr};
        r = r->next;
    }
}

void printList(LinkList L){
    ListNode* p = L->next;
    while(p){
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

void deleteList(LinkList& L){
    ListNode* p = L->next;
    while(p){
        ListNode* s = p;
        p = p->next;
        delete s;
    }
    delete L;
}

void splitLinkedList(LinkList L,LinkList& headA,LinkList& headB){
    headA = new ListNode{0,nullptr};
    headB = new ListNode{0,nullptr};
    ListNode* rA = headA;
    ListNode* rB = headB;
    ListNode* cur = L->next;
    bool toA = true;

    while(cur){
        ListNode*& tail = toA ? rA : rB;
        tail->next = new ListNode{cur->val,nullptr};
        tail = tail->next;
        cur = cur->next;
        toA = !toA;
    }
}

int main(){
    vector<int> arr;
    int temp;
    while(cin >> temp){
        arr.push_back(temp);
        if(cin.peek() == '\n') break;
    }

    LinkList L;
    createListFromArray(L,arr);
    LinkList headA,headB;
    splitLinkedList(L,headA,headB);
    deleteList(L);

    printList(headA),printList(headB);
    deleteList(headA),deleteList(headB);
    return 0;
}