做网站的软件有哪些,seo优化设计,中国服务器在外国网站有哪些,页面开发剑指 Offer#xff08;第2版#xff09;面试题 35#xff1a;复杂链表的复制 剑指 Offer#xff08;第2版#xff09;面试题 35#xff1a;复杂链表的复制解法1#xff1a;模拟 剑指 Offer#xff08;第2版#xff09;面试题 35#xff1a;复杂链表的复制
题目来源第2版面试题 35复杂链表的复制 剑指 Offer第2版面试题 35复杂链表的复制解法1模拟 剑指 Offer第2版面试题 35复杂链表的复制
题目来源48. 复杂链表的复刻
解法1模拟
算法
复制原始链表的节点 N 并创建新节点 N’把 N’ 链接到 N 的后面。设置复制节点的 random 指针。拆分链表把奇数位置的节点链接起来就是原始链表把偶数位置的节点链接起来就是复制链表最后返回复制链表的头节点。 PS少有的书上代码比其他解法要好的推荐书上解法拆分成三步走清晰明了。 代码
/*** Definition for singly-linked list with a random pointer.* struct ListNode {* int val;* ListNode *next, *random;* ListNode(int x) : val(x), next(NULL), random(NULL) {}* };*/
class Solution
{
public:ListNode *copyRandomList(ListNode *head){CloneListNodes(head);SetRandomPointer(head);return SplitList(head);}// 第一步复制原始链表的节点 N 并创建新节点 N把 N 链接到 N 的后面void CloneListNodes(ListNode *head){ListNode *p head;while (p){// 复制节点ListNode *clone new ListNode(0);clone-val p-val;clone-next p-next;clone-random nullptr;p-next clone;p clone-next;}}// 第二步设置复制节点的 random 指针void SetRandomPointer(ListNode *head){// 如果原始链表上的节点 N 的 random 指针指向 S// 则它的复制节点 N 的 random 指针指向 SListNode *p head;while (p){ListNode *clone p-next;if (p-random)clone-random p-random-next;p clone-next;}}// 第三步拆分链表ListNode *SplitList(ListNode *head){ListNode *p head;ListNode *cloneListHead nullptr;ListNode *clone nullptr;if (p){cloneListHead p-next;clone p-next;p-next clone-next;p p-next;}while (p){clone-next p-next;clone clone-next;p-next clone-next;p p-next;}return cloneListHead;}
};复杂度分析
时间复杂度O(n)其中 n 是原始链表的节点个数。算法遍历了每个节点。
空间复杂度O(n)其中 n 是原始链表的节点个数。算法创建了每个节点的副本。
