Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 212
  • Last Modified:

Single linked lists merge

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
RickHancock
Asked:
RickHancock
  • 2
1 Solution
 
jkrCommented:
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
 
jkrCommented:
Ooops, I forgot, then:

LisEntry* List3 =GetHeadOfList1(); // that now resembles the joined list.
0
 
itsmeandnobodyelseCommented:
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

Industry Leaders: 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!

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now