1.4 编写程序，输入若干正整数，按从小到大次序建立1个带头结点单链表，设计一个实现单链表分离算法的split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，其余结点来自原链表，分离后，原链表中只剩非偶数值所在结点，最后显示2个单链表，在程序退出前销毁单链表。要求split算法时间复杂性达到o（n）,程序不可存在内存泄漏。

### 回答1：
题目要求我们编写一个程序，输入若干正整数，按从小到大顺序建立1个带头结点单链表，设计一个实现单链表分离算法的split函数，将原单链表中值为偶数的结点分离出来形成一个新单链表，新单链表中头结点重新申请，请在程序退出前销毁单链表。要求split算法时间复杂度达到O(n)，程序不可存在内存泄漏。

### 回答2：
思路：

- 输入若干正整数，按从小到大次序建立一个带头结点单链表
- 分离原单链表的偶数节点，生成新的带头结点单链表
- 输出两个单链表，销毁原单链表和新单链表

第一步，建立如下单链表：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def createListNode(head: ListNode, nums: List[int]):
    for num in nums:
        node = ListNode(num)
        if head.next == None:
            head.next = node
        else:
            cur = head.next
            pre = head
            while cur and cur.val < num:
                pre = cur
                cur = cur.next
            pre.next = node
            node.next = cur

第二步，分离偶数节点，生成新单链表：

先遍历原单链表，将偶数节点放进新单链表。这里注意记录分离的偶数节点链的头结点，函数返回它；用prev指针记录当前节点的上一个节点，便于拼接列表。

时间复杂度: O(n) (n是总节点数)。

def split(head: ListNode) -> ListNode:
    node_even = ListNode(-1)
    even = node_even
    prev = head
    curr = head.next
    while curr:
        if curr.val % 2 == 0:
            prev.next = curr.next
            even.next = curr
            even = even.next
            curr = prev.next
        else:
            prev = prev.next
            curr = curr.next
    even.next = None
    return node_even

第三步，输出两个单链表，销毁原单链表和新单链表。

def printListNode(node):
    cur = node.next
    res = []
    while cur:
        res.append(cur.val)
        cur = cur.next
    print(res)

def destroyListNode(head: ListNode):
    cur = head.next
    while cur:
        tmp = cur.next
        del cur
        cur = tmp
    head.next = None

if __name__ == "__main__":
    nums = [2, 7, 1, 5, 6, 3, 4, 8, 9, 10]
    head = ListNode(-1)
    createListNode(head, nums)
    node_even = split(head)
    printListNode(head)
    printListNode(node_even)
    destroyListNode(head)
    destroyListNode(node_even)

完整代码如下：

### 回答3：
算法步骤：

（1）定义一个指向链表头结点的指针head和一个当前结点指针p。

（2）定义一个指向分离后新链表头结点的指针newHead和一个当前结点指针q。

（3）遍历链表，当当前结点的值为偶数时，将该结点从原链表上摘除，接入新链表中。同时更新head、p节点，newHead、q节点。

（4）事件复杂度是O(n)，插入新链表操作仅执行n/2次，与n无关，空间复杂度为O(1)。

下面是完整程序实现：

#include<iostream>
using namespace std;

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

void createlist(ListNode*& L)
{
    L = new ListNode(0);
    int x;
    cin >> x;
    while (x > 0)
    {
        ListNode* p = new ListNode(x);
        p->next = L->next;
        L->next = p;
        cin >> x;
    }
}

void printlist(ListNode* L)
{
    while (L->next != NULL)
    {
        cout << L->next->val << " ";
        L = L->next;
    }
    cout << endl;
}

void split(ListNode*& head, ListNode*& newHead)
{
    ListNode *p, *q;
    newHead = new ListNode(0);
    p = head; q = newHead;
    while (p->next != NULL)
    {
        if (p->next->val % 2 == 0)
        {
            q->next = p->next;
            p->next = p->next->next;
            q = q->next;
            q->next = NULL;
        }
        else
        {
            p = p->next;
        }
    }
}

void destroylist(ListNode*& L)
{
    ListNode* p;
    while (L != NULL)
    {
        p = L;
        L = L->next;
        delete p;
    }
}

int main()
{
    ListNode* head, * newHead;
    createlist(head);

    split(head, newHead);
    cout << "Original List: ";
    printlist(head);
    cout << "New List: ";
    printlist(newHead);

    destroylist(head);
    destroylist(newHead);
    return 0;
}