在一行中输出合并后新的有序链表，数字间用空格分开，开头和结尾不能有多余空格；若新链表为空，输出NULL。

在C++中，如果你有一个链表并想要将其转换成一个字符串，在一行中展示每个节点的值，数值之间用空格分隔，并且保证首尾无多余空格，同时处理空链表的情况，你可以这样做：

#include <sstream>

// 假设你的链表节点结构如下
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

std::string printListNode(ListNode* head) {
    if (head == NULL) {
        return "NULL";
    }

    std::stringstream ss; // 用于拼接字符串
    bool first = true; // 标记是否为第一个数

    while (head != NULL) {
        ss << (first ? "" : " ") << head->val; // 输出节点值，首元素前无空格
        first = false;
        head = head->next;
    }

    return ss.str(); // 返回最终拼接好的字符串
}

这个函数会遍历链表，当遇到非第一个节点时在其值前加上一个空格。如果是空链表，它会返回"NULL"。结果是一个包含所有节点值的字符串。

相关问题

7-3 两个有序链表序列的合并 分数 20 作者 DS课程组 单位 浙江大学 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

好的，这是一道关于链表合并的问题。我可以帮您解答。

首先，我们需要先定义一个链表节点的结构体，包含两个成员：一个数值 value，一个指向下一个节点的指针 next。代码如下：

struct ListNode {
    int value;
    ListNode* next;
};

接下来，我们可以定义一个函数 merge，输入为两个链表的头指针，输出为合并后链表的头指针。具体实现如下：

ListNode* merge(ListNode* head1, ListNode* head2) {
    // 如果两个链表中有一个为空，则直接返回另一个链表的头指针
    if (!head1) return head2;
    if (!head2) return head1;

    ListNode* p1 = head1;
    ListNode* p2 = head2;
    ListNode* newHead = new ListNode;
    ListNode* p3 = newHead;

    // 遍历两个链表，将较小值的节点插入到新链表中
    while (p1 && p2) {
        if (p1->value <= p2->value) {
            p3->next = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p2 = p2->next;
        }
        p3 = p3->next;
    }

    // 将未遍历完的链表接到新链表的末尾
    if (p1) p3->next = p1;
    if (p2) p3->next = p2;

    ListNode* ret = newHead->next;
    delete newHead;
    return ret;
}

在上述函数中，我们定义了三个指针：p1、p2、p3。p1 和 p2 分别指向两个链表的当前节点，p3 指向新链表的末尾。我们遍历两个链表，将较小值的节点插入到新链表中，直到其中一个链表遍历完。最后，我们将未遍历完的链表接到新链表的末尾。最后，我们将新链表的头节点的 next 指针返回，即为合并后链表的头指针。

完整代码如下：

已知两个非降序链表序列s1与s2，设计函数构造出s1与s2的交集新链表s3。 输入格式: 输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出null。

### 回答1：
算法思路：

1. 定义两个指针分别指向两个链表的头结点，比较两个指针所指节点的值，将较小值的指针向后移动一位。

2. 如果两个指针所指节点的值相等，则将该节点的值加入新链表，并将两个指针都向后移动一位。

3. 重复上述步骤，直到其中一个链表遍历完毕。

4. 如果新链表为空，则输出null，否则输出新链表的值。

Python 代码实现：

# 定义链表节点类
class ListNode:
    def __init__(self, val=, next=None):
        self.val = val
        self.next = next

# 定义函数构造出两个链表的交集新链表
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 定义新链表的头结点和尾结点
    dummy = ListNode()
    tail = dummy

    # 定义两个指针分别指向两个链表的头结点
    p1, p2 = headA, headB

    # 遍历两个链表，比较节点的值
    while p1 and p2:
        if p1.val < p2.val:
            p1 = p1.next
        elif p1.val > p2.val:
            p2 = p2.next
        else:
            # 如果两个节点的值相等，则将该节点的值加入新链表
            tail.next = ListNode(p1.val)
            tail = tail.next
            p1 = p1.next
            p2 = p2.next

    # 如果新链表为空，则输出null，否则输出新链表的值
    if dummy.next is None:
        return "null"
    else:
        return dummy.next.val

# 读入两个非降序链表
s1 = list(map(int, input().split()))
s2 = list(map(int, input().split()))

# 构造两个链表
headA = ListNode(s1[])
p1 = headA
for i in range(1, len(s1)):
    if s1[i] == -1:
        break
    node = ListNode(s1[i])
    p1.next = node
    p1 = node

headB = ListNode(s2[])
p2 = headB
for i in range(1, len(s2)):
    if s2[i] == -1:
        break
    node = ListNode(s2[i])
    p2.next = node
    p2 = node

# 构造交集新链表
s3 = getIntersectionNode(headA, headB)

# 输出交集新链表
print(s3)

### 回答2：
题目中要求我们输入两个非降序的链表，并将它们的交集构造为一个新链表输出。我们可以从链表的基本操作和链表的遍历两个方面来解决这个问题。

对于链表的基本操作，我们需要先定义一个链表节点的结构体，并实现链表的初始化、插入和删除等操作。

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

ListNode* createList() {
ListNode *head = new ListNode(-1);
return head;
}

void insertNode(ListNode *head, int val) {
ListNode *node = new ListNode(val);
node->next = head->next;
head->next = node;
}

void deleteNode(ListNode *head, ListNode *node) {
ListNode *prev = head;
while (prev->next != node) {
prev = prev->next;
}
prev->next = node->next;
delete node;
}

对于链表的遍历，我们可以使用两个指针分别指向两个链表的开头，然后进行比较。如果两个节点的值相等，就将这个节点插入到新链表中；否则，将值较小的节点指针往下移动一个节点。当其中一个链表已经遍历完毕，就退出循环并输出新链表。

ListNode* intersection(ListNode *s1, ListNode *s2) {
ListNode *cur1 = s1->next, *cur2 = s2->next;
ListNode *s3 = createList();
while (cur1 != NULL && cur2 != NULL) {
if (cur1->val == cur2->val) {
insertNode(s3, cur1->val);
cur1 = cur1->next;
cur2 = cur2->next;
} else if (cur1->val < cur2->val) {
cur1 = cur1->next;
} else {
cur2 = cur2->next;
}
}
if (s3->next != NULL) {
return s3->next;
} else {
return NULL;
}
}

最后，我们可以在主函数中实现输入两个链表，调用intersection函数，输出新链表。

int main() {
ListNode *s1 = createList();
ListNode *s2 = createList();
int val;
while (cin >> val && val != -1) {
insertNode(s1, val);
}
while (cin >> val && val != -1) {
insertNode(s2, val);
}
ListNode *s3 = intersection(s1, s2);
if (s3 == NULL) {
cout << "null" << endl;
return 0;
}
ListNode *cur = s3;
while (cur != NULL) {
cout << cur->val;
cur = cur->next;
if (cur != NULL) {
cout << " ";
}
}
cout << endl;
return 0;
}

### 回答3：
算法思路：

我们可以使用双指针来遍历两个链表，每次比较两个指针所指的元素大小，若相等则加入新链表并将两个指针同时后移，若不相等则将指向小的元素的指针后移。

若其中一个链表已经遍历完，则结束循环，返回新链表。若新链表为空，则输出“null”。

参考代码：