在存储两个链表的数组中进行压缩

Question

数组Arr(大小n)可以表示双链表。假设单元格有struct {int val, next, prev;}]

我有两个列表A和B存储在数组中。A有m个节点，B有n - m个节点。

这些分散的节点，我想重新排列它们，使A的所有节点都来自Arr[0] ..Arr[m-1]和rest在O(m)时间内由B的节点填充。

我想到的解决办法是:

• 迭代A，直到出现一个位于Arr[m-1]之外的节点
• 然后，迭代B，直到出现一个位于Arr[m]
之前的节点
• 交换这两个(包括操作它们及其邻居的下一个先前链接)。

但是在这种情况下，迭代的总次数是O(n + m)，因此应该有一个更好的答案。

p。史:这个问题出现在算法导论，第二版。问题10.3 - 5

Answer 1

如何遍历list A并将每个元素放置在Arr[0] ... Arr[m-1]中，显然将其位置与之前的位置交换，并更新prev/next链接。会有很多交换，但它将是O(m)，因为一旦你完成对 a (m迭代)的迭代，它的所有元素将位于(顺便说一下，按顺序)Arr的第一个m槽，因此B必须完全位于Arr的其余部分。

添加一些伪代码

a := index of head of A 
for i in 0 ... m-1
    swap Arr[i], Arr[a]
    a := index of next element in A
end

Answer 2

我认为"jw013"是正确的，但这个想法需要一些改进:

通过交换你正在改变Arr数组中元素的地址。所以你需要小心!

。假设我们有一个Arr，像:

索引:0 1 2 3 4

        | 2 | empty | 3 | empty | 1 |   (assume the link list is like  1 -> 2 -> 3)

所以Arr[4].next为0,Arr[0].next为2。

，但当你交换Arr[4]和Arr[0]，那么Arr[0].next是0。这不是我们想要发生的，所以我们应该考虑在交换指针时调整指针。

所以它的代码是:

 public static void compactify(int List_head , int Free , node [] array){
        int List_lenght ;
        
        List_lenght = find_listlenght(List_head , array);
        
        if(List_lenght != 0){ // if the list is not empty
            int a = List_head;
            for (int i = 0; i < List_lenght ; i++) {
                swap( array , a , i );
                a = array[i].next;
                print_mem(array);
            }
        }
         
       
    }

现在调用swap:

private static void swap(node[] array, int a, int i) {
        
        // adjust the next and prev of both array[a] and array[i]
        
        int next_a = array[a].next;
        int next_i = array[i].next;
        
        int prev_a = array[a].prev;
        int prev_i = array[i].prev;
        
        // if array[a] has a next adjust the array[next_a].prev to i
        if(next_a != -1)   
            array[next_a].prev = i;
        // if array[i] has a next adjust the array[next_i].prev to a
        if(next_i != -1)  
            array[next_i].prev = a;
        // like before adjust the pointers of array[prev_a] and array[prev_i] 
        if(prev_a != -1)
            array[prev_a].next = i;
        if(prev_i != -1)
            array[prev_i].next = a;
        
        node temp = array[a];
        array[a] = array[i];
        array[i] = temp;
        
    }