How do c++ combine two ordered linked lists

1. Title requirements

This is a classic job interview question that often asks you to write by hand or take a computer test.

Given that two lists, head1 and head2, are in order, please combine them into one that is still in order. The result is a linked list that contains all the nodes of head1 and head2, even if the node values are the same.

Note: no new space can be created to store the merged list. If you do this the first time, it's easy to think of using a new list to store the merged ordered list. Although this can be done, it does not conform to the conventional solution and the requirements of the interviewer.

2. Non-recursive implementation

Algorithm process:
Input: two ordered single linked lists head1 and head2;
Output: merged single linked list mergeHead;
Algorithm description:
(1) If head1 or head2 is an empty linked list, it will directly return another linked list;
(2) Select the node with small value of the current node in the linked list of head1 and head2, and connect it to the linked list of mergeHead;
(3) Repeat step 2 until the traversal of the linked list head1 or head2 is completed. The untraversed linked list is directly connected to the tail node of mergeHead.

Specific implementation is as follows:

#include <sstream>
#include <iostream>
using namespace std;

struct ListNode 
{ 
  int     value; 
  ListNode*  next;
  ListNode() {value=0;next=NULL;}
  ListNode(int value,ListNode* next = NULL):value(value),next(next){} 
};

//@brief: Non-recursively implements two ordered single linked lists 
//@ Note: The two lists need to be sorted from smallest to largest 
ListNode* mergeOrderedLinkedList(ListNode* head1,ListNode* head2)
{
  if (head1 == NULL) 
  { 
    return head2; 
  }
  else if(head2 == NULL) 
  { 
    return head1; 
  }

  ListNode* mergeHead = NULL; 
  if (head1->value<head2->value) 
  { 
    mergeHead=head1;
    head1=head1->next;
  } 
  else 
  { 
    mergeHead = head2; 
    head2 = head2->next; 
  } 
  ListNode* tmpNode = mergeHead; 
  while(head1&&head2)
  { 
    if(head1->value<head2->value) 
    { 
      mergeHead->next = head1; 
      head1 = head1->next; 
    } 
    else 
    { 
      mergeHead->next = head2; 
      head2 = head2->next; 
    } 
    mergeHead = mergeHead->next; 
  } 
  if (head1)
  { 
    mergeHead->next = head1; 
  } 
  if (head2) 
  { 
    mergeHead->next = head2; 
  }

  return tmpNode; 
}

// Print the list 
void printLinkedList(ListNode* head)
{
  while(head)
  {
    cout<<head->value<<" ";
    head=head->next;
  }
  cout<<endl;
}

int main(int argc,char* argv[])
{
  ListNode* head1=NULL,*curList1=NULL,*head2=NULL,*curList2=NULL;
  string strIn;
  int value;

  cout<<" Create a list 1 , enter the linked list in order from small to large 1 : "<<endl;
  getline(cin,strIn);
  stringstream ss(strIn);
  cout<<"ss0 strIn:"<<ss.str()<<endl;
  while(ss>>value)    // from string Is read as a space int
  {
    ListNode* newNode1=new ListNode;
    newNode1->value=value;
    if(head1==NULL && curList1==NULL)
    {
      head1=newNode1;
      curList1=newNode1;
    }
    else
    {
      curList1->next=newNode1;
      curList1=curList1->next;
    }
  }

  cout<<" Create a list 2 , enter the linked list in order from small to large 2 : "<<endl;
  getline(cin,strIn);
  ss.clear(); // empty 
  ss.str(""); // Empty content 
  ss<<strIn;  // Re-output to string
  cout<<"ss1 strIn:"<<ss.str()<<endl;
  while(ss>>value)    // from string Is read as a space int
  {
    ListNode* newNode2=new ListNode;
    newNode2->value=value;
    if(head2==NULL && curList2==NULL)
    {
      head2=newNode2;
      curList2=newNode2;
    }
    else
    {
      curList2->next=newNode2;
      curList2=curList2->next;
    }
  }

  // Merge two ordered linked lists 
  ListNode* mergeHead=mergeOrderedLinkedList(head1,head2);

  // Print the list 
  cout<<" Linked list after merging: "<<endl;
  printLinkedList(mergeHead);
}

Run the program and output the following results:

Input linked list 1 from small to large:
1 2 3 5
ss0 strIn:1 2 3 5
Input linked list 2 in small to large order:
3 4 5 6 7 8
ss1 strIn:3 4 5 6 7 8
Linked list after merging:
1 2 3 3 4 5 5 6 7 8

3. Recursive implementation

As you can see from the above merging of the two ordered lists, step (2) of each merge is the same, which leads to recursion. Specific implementation is as follows:

//@brief: Recursively implements two ordered single linked lists 
//@ Note: The two lists need to be sorted from smallest to largest 
ListNode* mergeOrderedLinkedListRecursion(ListNode* head1,ListNode* head2)
{
  if(head1 == NULL) 
  { 
    return head2; 
  }
  else if(head2 == NULL) 
  { 
    return head1; 
  }

  ListNode* mergeHead = NULL;
  if(head1->value<head2->value) 
  {
    mergeHead=head1;
    mergeHead->next=mergeOrderedLinkedListRecursion(head1->next,head2);
  }
  else
  {
    mergeHead=head2;
    mergeHead->next=mergeOrderedLinkedListRecursion(head1,head2->next);
  }
  return mergeHead;
}

The above is c++ how to combine two ordered linked lists in detail, more information about c++ to combine two ordered linked lists please pay attention to other related articles on this site!