建立两个带头结点单链表

好的，我来给你写一下建立两个带头结点单链表的代码。这里假设链表中存储的元素为整型数。

#include <iostream>
using namespace std;

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

ListNode *createList(){
    ListNode *head = new ListNode(0); // 头结点
    ListNode *cur = head;
    int n;
    cout << "输入链表长度：";
    cin >> n;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        ListNode *node = new ListNode(x);
        cur->next = node;
        cur = node;
    }
    return head;
}

int main(){
    ListNode *list1 = createList();
    ListNode *list2 = createList();
    return 0;
}

这个程序会提示你输入两个链表的长度，然后分别输入每一个节点的值，最后返回两个带头结点的链表头指针 list1 和 list2。

相关问题

设计一个算法，将一个结点值为自然数的带头结点单链表拆分为两个带头结点单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的带头结点单链表。

算法如下：

1. 定义两个新的带头结点单链表，分别为evenList和oddList。

2. 遍历原链表，如果结点的值为偶数，则将该结点插入evenList中；如果结点的值为奇数，则将该结点插入oddList中。

3. 遍历完原链表后，将oddList插入到evenList的末尾。

4. 返回evenList和oddList。

代码实现如下：

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

pair<ListNode*, ListNode*> splitList(ListNode* head) {
    ListNode* evenList = new ListNode(0);
    ListNode* oddList = new ListNode(0);
    ListNode* evenTail = evenList;
    ListNode* oddTail = oddList;
    ListNode* cur = head->next;
    while (cur != NULL) {
        if (cur->val % 2 == 0) {
            evenTail->next = cur;
            evenTail = evenTail->next;
        } else {
            oddTail->next = cur;
            oddTail = oddTail->next;
        }
        cur = cur->next;
    }
    evenTail->next = oddList->next;
    oddTail->next = NULL;
    return make_pair(evenList, oddList);
}

设有带头结点单链表A和B，其结点均已按值升序排列，编写一个算法将他们合并成一个按值升序排列的带头结点单链表。

要合并两个已按值升序排列的带头结点单链表A和B，可以创建一个新的链表，并通过迭代或递归的方式将它们连接起来。这里提供一种简单的迭代方法：

1. 创建新链表C，初始化为一个空头结点。
2. 定义两个指针，分别指向A和B的头结点。
3. 比较两个当前指针所指节点的值：
- 如果A的值小于或等于B的值，将A的下一个节点添加到新链表C中，然后移动A指针。
- 否则，将B的下一个节点添加到新链表C中，然后移动B指针。
4. 当其中一个链表遍历完（即为空），将另一个链表剩余的部分直接添加到新链表的末尾。
5. 新链表C的头结点就是最终合并后的有序链表。

下面是伪代码描述：

def merge_sorted_lists(headA, headB):
    if not headA: return headB
    if not headB: return headA

    dummy = ListNode(0)  # 创建虚拟头结点
    tail = dummy

    while headA and headB:
        if headA.val <= headB.val:
            tail.next = headA
            headA = headA.next
        else:
            tail.next = headB
            headB = headB.next
        tail = tail.next

    # 将剩余的链表添加到新链表末尾
    if headA:
        tail.next = headA
    elif headB:
        tail.next = headB

    return dummy.next