How to combine 2 double linked list by turns

Question

I have 2 double linked list here and i want to combine into the new list but i have a problem to make it by turns. Here's my code so far :

class NodeDLL {

public Object data;
public NodeDLL next;
public NodeDLL prev;

public NodeDLL() {
    next = null;
}}

public class DoubleLinkList {

private NodeDLL head, tail;
private int counter, pos;

public DoubleLinkList() {
    head = null;
    tail = null;
    counter = -1;
    pos = 0;
}


public void InsertFirst(Object dt) {
    NodeDLL newNode = new NodeDLL();
    newNode.data = dt;
    if (head == null) {
        newNode.prev = head;
        newNode.next = tail;
        head = newNode;
        tail = newNode;
        counter = 0;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;

    }
    counter++;
}

public static DoubleLinkList combine(DoubleLinkList L1, DoubleLinkList L2) {

    DoubleLinkList L3 = new DoubleLinkList();
    DoubleLinkList L4 = new DoubleLinkList();

    while (L1.head != null) {
        L3.InsertFirst(L1.head.data);
        L1.head = L1.head.next;
    }
    while (L2.head != null) {
        L3.InsertFirst(L2.head.data);
        L2.head = L2.head.next;
    }
    while (L3.head != null) {
        L4.InsertFirst(L3.head.data);
        L3.head = L3.head.next;
    }
    return L4;

}

 public void Print(String kom) {
    System.out.println(kom);
    NodeDLL p = head;
    while (p != tail.next) {
        System.out.print(p.data + " <-> ");
        p = p.next;
    }
    System.out.println();
}

public static void main(String s[]) {

    DoubleLinkList dll2 = new DoubleLinkList();
    dll2.InsertFirst("A");
    dll2.InsertFirst("B");
    dll2.InsertFirst("C");
    dll2.InsertFirst("D");
    dll2.InsertFirst("E");
    dll2.InsertFirst("F");
    dll2.Print("Linked List 1");
    System.out.println("");

    DoubleLinkList dll3 = new DoubleLinkList();
    dll3.InsertFirst(1);
    dll3.InsertFirst(2);
    dll3.InsertFirst(3);
    dll3.InsertFirst(4);
    dll3.InsertFirst(5);
    dll3.InsertFirst(6);
    dll3.Print("Linked List 2");
    System.out.println("");

    DoubleLinkList NewList= DoubleLinkList.combine(dll2, dll3);
    NewList.Print("Result");
}}

This code will show :

Linked List 1

F <-> E <-> D <-> C <-> B <-> A <->

Linked List 2

6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <->

Result

F <-> E <-> D <-> C <-> B <-> A <-> 6 <-> 5 <-> 4 <-> 3 <-> 2 <-> 1 <->

expected output:

F <-> 6 <-> E <-> 5 <-> D <-> 4 <-> C <-> 3 <-> B <-> 2 <-> A <-> 1

Answer 1

/**
 * This method takes two DoublyLinkedList's and combines them one into one
 * list with alternating items from each input lists.
 *
 * @param     L1   the first linked list
 * @param     L2   the second linked list
 * @return    L3   the merged linked list
 */
public static DoubleLinkList combine(DoubleLinkList L1, DoubleLinkList L2) {
    DoubleLinkList L3 = new DoubleLinkList();
    DoubleLinkList L4 = new DoubleLinkList();

    // insert both list until the shorter list reaches its end
    while (L1.head != null && L2.head != null) {
        L4.InsertFirst(L1.head.data);
        L4.InsertFirst(L2.head.data);
        L1.head = L1.head.next;
        L2.head = L2.head.next;
    }

    // now check which list is longer
    if (L1.head == null && L2.head != null)
        L1.head = L2.head;

    // now just insert the rest of the items from the longer list
    while (L1.head != null) {
        L4.InsertFirst(L1.head.data);
        L1.head = L1.head.next;
    }

    // now reverse it by inserting this list into another list
    while (L4.head != null) {
        L3.InsertFirst(L4.head.data);
        L4.head = L4.head.next;
    }

    return L3;
}

Why don't you implement a method that just inserts at the end of a list? This way you don't need to do the last while loop to reverse the list.

Answer 2

Since I don’t have your DoubleLinkedList class, I have not been able to try it out, so there’s probably at least a typo or two:

while (L1.head != null && L2.head != null) {
    // insert one element from each list
    L3.InsertFirst(L1.head.data);
    L1.head = L1.head.next;
    L3.InsertFirst(L2.head.data);
    L2.head = L2.head.next;
}

If the lists may have different lengths, you will probably want to insert this loop before the loops you already have; keep them to make sure that any elements in the longer list are included.