拷贝带有随机指针的链表

拷贝带有随机指针的链表

---

# 算法描述


问题描述：拷贝“随机链表”，即节点带有一个指针可能指向链表随机另一个节点的链表。

解法1：一般的简单蛮力算法，可完成该功能，但时间复杂度为 O(n*m)。步骤：

 a 遍历链表一遍，完成拷贝链表与初始化next指针。遍历链表一遍M，M为节点个数。
 b 查找原链表的每一random指针对应节点，需要遍历旧链表直至找到匹配并记录偏移位置pos。遍历链表一遍M'，M' <= M且可变。
 c 根据偏移位置pos，在新链表对应节点的random指针赋值。遍历链表一遍M'，M' <= M可可变。
 d 重复b c操作，直至链表节点的random指针均赋值。该重复操作M次。
btw. 显然以上做法为最最低效。


解法2：较高效的算法，相比时间复杂度为O(m)。具体操作，需要遍历源链表三遍。包括拷贝链表+复制随机指针+回复源链表NEXT指针。算法步骤，复制完链表，遍历两遍即完成拷贝操作。详细步骤见下：

a. ABCD是原来的链表，A’B’C’D’是复制的链表，第一遍扫描顺序复制next指针，
b. 把ABCD的next分别指向A’B’C’D’，将A’的next指针指向B，B’的next指针指向C，依次类推。
c. 复制random指针： A’->random=A->random->next
d. 恢复:A->next=A’->next; A’->next=A’->next->next;



# 算法实现（C源码）

struct random_list_node
{
random_list_node()
: value(0), next_ptr(NULL), random_ptr(NULL)
{}
random_list_node(int v)
: value(v), next_ptr(NULL), random_ptr(NULL)
{}
~random_list_node() {}


int value;
random_list_node* next_ptr;
random_list_node* random_ptr;
};


typedef random_list_node* random_list;




random_list_node* copy_random_list(random_list_node* head_ptr)
{
if (NULL == head_ptr) return NULL;


random_list_node* new_head_ptr = new random_list_node;
new_head_ptr->value = head_ptr->value;
new_head_ptr->next_ptr = head_ptr->next_ptr;
head_ptr->next_ptr = new_head_ptr;
// copy random_list
random_list_node* move_ptr = new_head_ptr->next_ptr;
while (move_ptr)
{
random_list_node* new_node = new random_list_node;
new_node->value = move_ptr->value;
new_node->next_ptr = move_ptr->next_ptr;
move_ptr->next_ptr = new_node;
move_ptr = new_node->next_ptr;
}


// scan random_list twice, for random_ptr and next_ptr.
move_ptr = head_ptr;
while (move_ptr)
{
random_list_node* new_move_ptr = move_ptr->next_ptr;
if (move_ptr->random_ptr)
new_move_ptr->random_ptr = move_ptr->random_ptr->next_ptr;


assert(NULL != new_move_ptr);
move_ptr = new_move_ptr->next_ptr;
//new_move_ptr = move_ptr->next_ptr;
}


move_ptr = head_ptr;
random_list_node* new_move_ptr = move_ptr->next_ptr;
while (new_move_ptr)
{
move_ptr->next_ptr = new_move_ptr->next_ptr;
if (new_move_ptr->next_ptr)
new_move_ptr->next_ptr = new_move_ptr->next_ptr->next_ptr;
move_ptr = move_ptr->next_ptr;
new_move_ptr = new_move_ptr->next_ptr;
}


return new_head_ptr;
}

# 附
该算法完整的C程序示例代码放在Github，可参见。
可参考其他网友同仁的博文，包括其图示说明，在这里。

（完）