C++合并两个链表算法出现Segmentation Fault问题求助

Hey there! Segmentation faults (segfaults) when merging linked lists are such a common gotcha—let’s walk through the most likely reasons you’re hitting this, and how to fix them:

Common Culprits & Fixes #

• Dereferencing a null pointer
  This is the #1 cause. You probably forgot to check if a node pointer is nullptr before accessing its val or next member. For example:

  • If you have a loop like while (list1->next != nullptr) but don’t first check if list1 itself is nullptr, you’ll crash when list1 is empty.
  • When one list runs out of nodes, you might still try to access its values instead of attaching the remaining nodes from the other list.

• Uninitialized pointers
  If you’re trying to build the merged list without properly setting up a starting point, you’ll hit a segfault. For instance, if you declare Node* merged = nullptr; and then immediately do merged->val = ..., you’re writing to invalid memory.
  The easy fix here is to use a dummy node—a temporary node that acts as a placeholder for the start of your merged list. It lets you avoid dealing with null pointer initialization headaches.

• Loop condition missteps
  Off-by-one errors or incorrect loop checks can make you traverse past the end of a list. For example, using while (list1 != nullptr || list2 != nullptr) without handling cases where one list is already empty will lead to trying to access nodes that don’t exist.

Example Working Code (Using Dummy Node) #

Here’s a solid implementation that avoids these pitfalls—this should work for the HackerRank problem:

struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

Node* mergeLists(Node* head1, Node* head2) {
    // Dummy node to simplify edge cases
    Node dummy(0);
    Node* current = &dummy;
    
    // Traverse both lists while both have nodes
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->data <= head2->data) {
            current->next = head1;
            head1 = head1->next;
        } else {
            current->next = head2;
            head2 = head2->next;
        }
        current = current->next;
    }
    
    // Attach any remaining nodes from either list
    current->next = (head1 != nullptr) ? head1 : head2;
    
    return dummy.next;
}

Why This Works: #

• The dummy node gives us a valid starting point, so we never have to worry about writing to a null pointer.
• We always check if head1 and head2 are non-null before accessing their members.
• After the loop, we safely attach the remaining nodes from whichever list isn’t empty.

If you’re still hitting a segfault, double-check if you’re accidentally modifying the original lists in a way that breaks their structure, or if you’re returning a pointer to a local variable (though the dummy node here is on the stack, but we return dummy.next which points to heap-allocated nodes, so that’s safe).

内容的提问来源于stack exchange，提问作者Platus