左神算法基础class3—题目13复制含有随机指针节点的链表

本文主要是介绍左神算法基础class3—题目13复制含有随机指针节点的链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目:复制含有随机指针节点的链表

【题目】 一种特殊的链表节点类描述如下：
public class Node
{
public int value;
public Node next;
public Node rand;
public Node(int data) { this.value = data; }
}
Node类中的value是节点值，next指针和正常单链表中next指针的意义一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指针可 能指向链表中的任意一个节点，也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个 函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。
进阶：不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)内完成原问题要实现的函数。

2.分析

题目给定的数据结构如上图,链表有rand、next两个指针，next指针1->2->3。1的rand指针指向3,2指向1,3的rand指向null，要求复制一份整个链表。
方法一：使用哈希表（哈希表不太熟，以后再补）
方法二：再原来链表基础上修改
思路：单独看1、2、3这三个节点如下图所示，考虑在每个节点后面加入三个新的节点1、2、3连成一个大链表，再分别复制这三个节点，最后分离复制的节点形成一个新链表达到题目要求

3.核心代码

（1）生成题设链表

typedef struct ListNode
{int val;ListNode *next;ListNode *rand;
}*List;

①生成头节点

List MakeEmpty()
{List head = (List)malloc(sizeof(ListNode));head->next = NULL;return head;
}

②尾插法插入数据

void insert_next(List head,int num)
{//p是新加入的节点List p =  (List)malloc(sizeof(ListNode));p->val = num;p->next = NULL;p->rand = NULL;List r = head;while(r->next != NULL)//r指向末尾{r = r->next;}r->next = p;//p加入链表
}

③加入rand指针
直接在主函数中添加1->3,2->1,3->NULL

	List cur = head->next;cur->rand = cur->next->next;cur->next->rand = cur;cur->next->next->rand = NULL;

（2）加入新节点

由于加入新节点后，原来链表会被打断，所以需要提前记录下一个节点的位置nex，本步骤相当于在当前位置插入节点。

//加入链head = head->next;List cur = head;//cur当前节点List nex = NULL;while(cur != NULL){nex = cur->next;List p =  (List)malloc(sizeof(ListNode));cur->next = p;p->next = nex;cur = nex;}

（3）复制新节点的值及rand指针

例如1->3,那么1*->3*,使用两个指针分别指向当前节点和新加入的节点1、1*。1应该指向1->rand(也就是3)->next(即3)，相当于新节点的rand指向旧节点的rand的next。当然，3的rand指向NULL，就没有next指针了，需要加个判断不然会报错。

	//copycur = head;List cur_copy = NULL;//新节点while(cur != NULL ){cur_copy = cur->next;cur_copy->rand = cur->rand == NULL ? NULL : cur->rand->next;//拷贝指针cur_copy->val = cur->val;//拷贝值cur = cur_copy->next;}

（4）分离拷贝的部分

直接把新节点连起来，也是通过两个指针cur和cur_copy

//分离拷贝的部分List res = head->next;//返回res新节点位置cur = head;while(cur != NULL){nex = cur->next->next;//记录下一个旧节点cur_copy = cur->next;cur_copy->next = nex == NULL ? NULL : cur_copy->next->next;cur = nex;//cur相当于只在旧节点1,2,3之间寻找}

4.完整代码

#include<iostream>
using namespace std;typedef struct ListNode
{int val;ListNode *next;ListNode *rand;
}*List;List copy_list(List head)
{//加入链head = head->next;List cur = head;//当前节点List nex = NULL;while(cur != NULL){nex = cur->next;List p =  (List)malloc(sizeof(ListNode));cur->next = p;p->next = nex;cur = nex;}//copycur = head;List cur_copy = NULL;while(cur != NULL ){cur_copy = cur->next;cur_copy->rand = cur->rand == NULL ? NULL : cur->rand->next;cur_copy->val = cur->val;cur = cur_copy->next;}//分离拷贝的部分List res = head->next;cur = head;while(cur != NULL){nex = cur->next->next;//记录下一个旧节点cur_copy = cur->next;cur_copy->next = nex == NULL ? NULL : cur_copy->next->next;cur = nex;//cur相当于只在旧节点1,2,3之间寻找}return res;
}void insert_next(List head,int num)
{List p =  (List)malloc(sizeof(ListNode));p->val = num;p->next = NULL;p->rand = NULL;List r = head;while(r->next != NULL){r = r->next;}r->next = p;
}List MakeEmpty()
{List head = (List)malloc(sizeof(ListNode));head->next = NULL;return head;
}int main()
{List head = MakeEmpty();insert_next(head,5);insert_next(head,7);insert_next(head,9);List cur = head->next;cur->rand = cur->next->next;cur->next->rand = cur;cur->next->next->rand = NULL;List res = copy_list(head);system("pause");return 0;
}

这篇关于左神算法基础class3—题目13复制含有随机指针节点的链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---