如何交替合并两个双向链表

Question

如何交替合并两个双向链表

3

我这里有两个双向链表，我想将它们合并成一个新的链表，但是我在轮流进行合并时遇到了问题。以下是我目前的代码：

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 <-> 结果 F <-> 6 <-> E <-> 5 <-> D <-> 4 <-> C <-> 3 <-> B <-> 2 <-> A <-> 1

期望输出：

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

- nanang

1

欢迎来到 Stack Overflow！请查看我们的 SO 问题清单来帮助您提出好问题，从而得到好答案。 - Joe C

请发布您的DoubleLinkedList类，并发布上述输入的预期输出。A->1->B->2->C->3->D->4->E->5->F->6。是您的预期输出吗？ - denvercoder9

你确定处理“next”只能产生可用的“DoubleLinkList”吗？试着更详细地描述“轮流”，这可能会给你编写代码的想法。 - greybeard

@RafiduzzamanSonnet 我已经编辑了我的帖子，希望你能理解我所询问的内容。 - nanang

@老程序员当然不是，那只是我的代码的一部分。我已经发布了完整的代码。 - nanang

2个回答

0

由于我没有你的DoubleLinkedList类，所以我还没有尝试过它，所以可能至少有一个或两个错别字：

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

如果列表的长度可能不同，您可能希望在已有的循环之前插入此循环；保留它们以确保包括较长列表中的任何元素。

- Ole V.V.

我已经发布了完整的代码，而且列表可能具有不同的长度。我现在得到了预期的输出。 - nanang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- denvercoder9 · Accepted Answer

/**
 * 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循环来反转列表了。