压缩存储2个链表的数组-Java 学习之路

数组Arr（大小n）可以表示双向链表 . [假设细胞有结构{int val，next，prev; }]

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

这些节点被分散，我想重新排列它们，使得A的所有节点都来自Arr [0] .. Arr [m-1]并且其余由B的节点填充，在O（m）时间内 .

我遇到的解决方案是：

迭代A直到出现超出Arr [m-1]的节点
然后，迭代B直到出现在Arr [m]之前的节点
交换两个（包括操纵他们和他们的邻居的下一个prev链接） .

但是在这种情况下，迭代总数是O（n m） . 因此应该有一个更好的答案 .

P.S：这个问题发生在Introduction to Algorithms, 2nd edition . 问题10.3-5

2 回答

0
如何迭代列表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
```
回复于 2024-05-07T01:10:42+08:00

我认为“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;
        
    }

回复于 2024-05-07T01:10:42+08:00

压缩存储2个链表的数组

2 回答

相关问题