变换双向链表

Question

我需要以这种方式转换DLL :给定n(节点数)和表示两个间隔a，b和b，c的四个整数(a，b，c，d)。例如：

N: 7

Input list:

1 2 3 4 5 6 7

a,b = 2 3
c,d = 5 6

我需要做的是交换给定间隔中的节点，因此输出应该是：

1 **5 6** 4 **2 3** 7

如您所见，具有元素2和3的节点将位置与5和6互换。

输入输入的其他方式可以是这样的：

N:5

Input: 10 50 40 25 1

a, b: 10 10
c, d: 40 1

Output: 40 25 1 50 10

这意味着间隔可以以相同的数字开始和结束。

编辑:请注意，间隔可以不同，即a，b可以有3个节点，c，d可以有更多或更少，或者相同数量的节点。

以下是我到目前为止所做的工作。我只获取了给定的节点(a，b，c，d)后继节点和前置节点，但我需要以某种方式交换它们。下面是该函数的代码。

private static DLL<Integer> intervals(DLL<Integer> list, int a, int b, int c, int d) {


        DLLNode<Integer> temp = lista.getFirst();
        DLLNode<Integer> temp1;
        DLLNode<Integer> temp2;
        DLLNode<Integer> temp3;
        DLLNode<Integer> temp4;
        while(temp != null){
            if(temp.element == a){
                temp1 = temp.pred;
            }
            if(temp.element == b){
                temp2 = temp.succ;
            }
            if(temp.element == c){
                temp3 = temp.pred;
            }
            if(temp.element == d){
                temp4 = temp.succ;
            }
            temp = temp.succ;
        }
        return list;
    }

Answer 1

您可以在返回列表之前执行以下操作。

DLLNode<Integer> a = temp1.succ;
DLLNode<Integer> b = temp2.pred;
DLLNode<Integer> c = temp3.succ;
DLLNode<Integer> d = temp4.pred;

temp1.succ = temp3.succ;
temp3.pred = temp1;

temp4.succ = a;
a.pred = temp4;

b.succ = c;
c.pred = b;

Answer 2

你就快到了！假设列表如下所示：

[ ... p, a ... b, q ... r, c ... d, s ... ]
         ^^^^^^^           ^^^^^^^

您已经提取了包含p, q, r, s的节点。现在，您想要交换带下划线的区域。使p = a.pred将其succ指向c，反之亦然。类似地，将d链接到q；然后将r链接到a，将b链接到s。

Answer 3

好了，伙计们，我解决了这个问题，这是完整的代码，很容易理解。

private static DLL<Integer> intervals(DLL<Integer> list, int a, int b, int c, int d) {



        DLLNode<Integer> temp =l ist.getFirst();
        DLL<Integer> tmp2=new DLL<Integer>();
        DLL<Integer> tmp3=new DLL<Integer>();
        DLL<Integer> tmp4=new DLL<Integer>();
        DLL<Integer> newList =new DLL<Integer>();
        while(temp .element!=a)
        {
            nova.insertLast(temp .element);
            temp = temp.succ;
        }
        tmp2.insertLast(temp.element);
        temp =temp.succ;
        while(temp.pred.element!=b)
        {
            tmp2.insertLast(temp.element);
            temp=temp.succ;
        }
        while(temp.element!=c)
        {
            tmp3.insertLast(temp.element);
            pom=pom.succ;
        }
        while(temp!=null&&temp.pred.element!=d)
        {
            tmp4.insertLast(temp.element);
            temp=temp.succ;
        }

        DLLNode<Integer> node2=tmp2.getFirst();
        DLLNode<Integer> node3=tmp3.getFirst();
        DLLNode<Integer> node4=tmp4.getFirst();

        while(node4 != null)
        {
            newList.insertLast(node4.element);
            node4=node4.succ;
        }
        while(node3 != null)
        {
            newList.insertLast(node3.element);
            node3=node3.succ;
        }
        while(node2 != null)
        {
            newList.insertLast(node2.element);
            node2=node2.succ;
        }
        while(pom != null)
        {
            newList.insertLast(pom.element);
            pom=pom.succ;
        }
        list = newList;
        return list;
    }