?
Solved

Single linked lists merge

Posted on 2005-03-25
3
Medium Priority
?
211 Views
Last Modified: 2010-04-01
What is the best way to merge 2 single linked list (list1 and list 2) into a 3rd list (list3).  The lists are of type INT.  These single linked list are not arrays and are created with a Struct and pointers.
0
Comment
Question by:RickHancock
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
3 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 13632766
You'd have the last entry of List1 point to the head (1st) entry of List2, e.g.

struct ListEntry {

    int data;
    struct ListEntry* pNext;
};

ListEntry* List1 = GetHeadOfList1();
ListEntry* List2 = GetHeadOfList2();

// go to the end of List1
while ( List1->pNext != NULL) List1 = List1->pNext;

// Set 'pNext' to the head of list2 to join them

List1->pNext = List2;
0
 
LVL 86

Accepted Solution

by:
jkr earned 750 total points
ID: 13632776
Ooops, I forgot, then:

LisEntry* List3 =GetHeadOfList1(); // that now resembles the joined list.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13643783
If the lists were sorted you need something like that:

struct Node
{
    int data;
    Node* pNext;
    Node(int d) : data(d), pNext(NULL) {}
    ~Node() { delete pNext; }
};

class SList
{
      Node* pHead;
      Node* pLast;
public:
      SList() : pHead(NULL), pLast(NULL) {}
      ~SList() { delete pHead; }
      void Add(int d)
      {
           Node* p = new Node(d);
           if (pHead == NULL)
                pHead = pLast = p;
           else
           {
                pLast->pNext = p;
                pLast = p;
            }
      }
      SList(const SList& list1, const SList2& list2)
      {
           Node* p1 = list.pHead;
           Node* p2  = list2.pHead;
           while (p1 != NULL || p2 != NULL)
           {
                if (p1 == NULL && p2 == NULL)
                {
                      if (p1->data < p2->data)
                      {
                           Add(p1->data);
                           p1 = p1->pNext;
                       }
                       else
                      {
                           Add(p2->data);
                           p2 = p2->pNext;
                       }
                 }
                 else if (p1 != NULL)
                 {
                       Add(p1->data);
                       p1 = p1->pNext;
                 }
                 else
                 {
                       Add(p2->data);
                       p2 = p2->pNext;
                  }
           }
      }
};

Regards, Alex
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question