链表拼接时原链表被意外改变（leetcode21题）

Question

我写了一段拼接list1，list2的代码，在输出时发现我的list1从1 3 5 变成了 1 2 3 4 5 6，list2也被修改了，但是我在代码里没有改变但 list1和list2 本身的结构，为什么输出时不一样了呢

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

//结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
//合并链表
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next;
            }
            else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list2 == nullptr) tail->next = list1;
        if (list1 == nullptr) tail->next = list2;
        ListNode* result = head->next;
        delete head;
        return result;     
    }
};
//输出链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
int main() {
    Solution solution;
    ListNode* list1 = new ListNode(1, new ListNode(3, new ListNode(5)));
    ListNode* list2 = new ListNode(2, new ListNode(4, new ListNode(6)));
    ListNode* mergedList1 = solution.mergeTwoLists(list1, list2);
    cout << "连接后的链表: ";
    printList(mergedList1);
    cout << "链表1: ";
    printList(list1);
    cout << "链表2: ";
    printList(list2);
    return 0;
}

输出：
连接后的链表: 1 2 3 4 5 6
链表1: 1 2 3 4 5 6
链表2: 2 3 4 5 6

请求解答！

Answer 1

在你的代码中，list1 和 list2 是通过指针传递给 mergeTwoLists 方法的。在方法中，你对这些链表进行了合并操作，但没有创建新的节点，而是直接修改了原始链表的指针指向。

因此，当你在 printList 方法中遍历 list1 和 list2 时，实际上是遍历了合并后的链表 mergedList1。这就是为什么输出结果中 list1 和 list2 的值也被修改了。

如果你想保留原始链表的结构，可以在 mergeTwoLists 方法中创建新的节点，并将原始链表的值复制到新的节点上。这样，合并后的链表将与原始链表相互独立。

以下是修改后的代码示例：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                tail->next = new ListNode(list1->val);
                list1 = list1->next;
            }
            else {
                tail->next = new ListNode(list2->val);
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list2 == nullptr) tail->next = list1;
        if (list1 == nullptr) tail->next = list2;
        ListNode* result = head->next;
        delete head;
        return result;     
    }
};

这样修改后，list1 和 list2 将保留其原始结构，输出结果也将正确显示。