java - 如何轮流组合2个双向链表

Question

我这里有 2 个双向链表，我想合并到新列表中，但轮流创建时遇到问题。到目前为止，这是我的代码:

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");
}}

此代码将显示:

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 <->

预期输出:

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;
}

为什么不实现一个只在列表末尾插入的方法？这样您就不需要执行最后一个 while 循环来反转列表。