ok, i need to write a function called merge_lists that take two call-by- reference arguments that are pointer variables that point to the heads of linked lists of values of type int. the two linked lists are assumed to be sorted so that the # at the head is the smallest #, the # in the next node is the next smallest, and so forth. the function returns a pointer to the head of a new linked list that contains all of the noids in the original two lists. the noids in this longer list are also sorted from smaller to largest values. when the function call ends, the two pointer variable argument should have the value NULL


// project 11.cpp : Defines the entry point for the console application.
// MergeLists.cpp   
// A  program that creates two ordered linked lists from user input 
// and merges them into a single ordered list.
// **************************************************************************

#include <iostream>
using namespace std;

struct Node
  int data;
  Node *link;

typedef Node* NodePtr;

void addToEnd(NodePtr& head, int val);
//PRECONDITION: head has been initialized, val holds the value to add to the list
//POSTCONDITION: A new node containing val has been added to the end of the list.

void printList(NodePtr head);
//PRECONDITION: head has been initialized
//POSTCONDITION: The list has been printed to the standard output

NodePtr mergeLists(NodePtr& list1, NodePtr& list2);
//PRECONDITION: The nodes in list1 and list2 contain values in increasing order
//POSTCONDITION: Returns a list containing the ordered merge of list1 and list2;
// list1 and list2 are NULL

int main()
  int nextInt;

  //create two empty lists
  NodePtr list1 = NULL;
  NodePtr list2 = NULL;

  //Put values in list1
  cout << "Enter integers in sorted order for first list, -1 to end\n";
  cin >> nextInt;
  while (nextInt != -1)
      addToEnd(list1, nextInt);
      cin >> nextInt;

  //Put values in list2
  cout << "Enter integers in sorted order for second list, -1 to end\n";
  cin >> nextInt;
  while (nextInt != -1)
      addToEnd(list2, nextInt);
      cin >> nextInt;

  //merge lists
  NodePtr mergedList = mergeLists(list1, list2);

  //print lists
  cout << "Merged list\n";
  cout << "\nOriginal lists";
  cout << "\nlist1: ";
  cout << "\nlist2: ";
  cout << endl;

void addToEnd(NodePtr& head, int val)
  //create and fill node to add to list
  NodePtr newNode = new Node;
  newNode->data = val;
  newNode->link = NULL;

  if (head == NULL)
    head = newNode;
      //find last node in list
      NodePtr temp = head;
      while (temp->link != NULL)
    temp = temp->link;

      //make it point to the new node
      temp->link = newNode;

void printList(NodePtr head)
  if (head != NULL)
      cout << head->data << " ";
return 0;

could you not take the first list and traverse the second list, adding the items to the first list untill you reach the end of the second list? once you have the list it would be easy to sort, possably by temporarily converting the list to an array (or overloading the [] operator....) and sorting the numbers, the converting it back to a list. :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.