【Leetcode -138.复制带随机指针的链表 -2130.链表最大孪生和】

Leetcode -138.复制带随机指针的链表

题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。 返回复制链表的头节点。 用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1： 输入：head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] 输出： [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]

示例 2： 输入：head = [[1, 1], [2, 1]] 输出： [[1, 1], [2, 1]]

示例 3： 输入：head = [[3, null], [3, 0], [3, null]] 输出： [[3, null], [3, 0], [3, null]]

提示： 0 <= n <= 1000

• 10^4 <= Node.val <= 10^4 Node.random 为 null 或指向链表中的节点。

思路：思路是在原链表上动，将拷贝节点插入原节点后面，插入原链表节点的原因是，当前拷贝节点的 random 就是原节点的 random 的 next，方便复制拷贝节点的 random ；最后将原链表和拷贝节点分离，恢复原链表；

拷贝节点插入原节点后面：

复制random节点：

		struct Node* copyRandomList(struct Node* head)
		{
		    struct Node* cur = head;
		
		    //拷贝节点插入原节点后面
		    while (cur)
		    {
		        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
		        struct Node* next = cur->next;
		        copy->val = cur->val;
		        cur->next = copy;
		        copy->next = next;
		
		        cur = next;
		    }
		
		    //将拷贝节点插入原节点后面之后，当前拷贝节点的 random 就是原节点的 random 的 next
		    //复制random节点
		    cur = head;
		    while (cur)
		    {
		        struct Node* copy = cur->next;
		        if (cur->random == NULL)
		        {
		            copy->random = NULL;
		        }
		        else
		        {
		            copy->random = cur->random->next;
		        }
		        cur = copy->next;
		    }
		
		    //将复制链表和原链表分开
		    cur = head;
		    struct Node* copyhead = NULL, * copytail = NULL;
		    while (cur)
		    {
		        struct Node* copy = cur->next, * next = copy->next;
		        if (copyhead == NULL)
		        {
		            copyhead = copytail = copy;
		        }
		        else
		        {
		            copytail->next = copy;
		            copytail = copytail->next;
		        }
		
		        //恢复原链表
		        cur->next = next;
		        cur = next;
		    }
		
		    return copyhead;
		}

Leetcode -2130.链表最大孪生和

题目：在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n - 1 - i) 个节点 。 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。 孪生和 定义为一个节点和它孪生节点两者值之和。 给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1： 输入：head = [5, 4, 2, 1] 输出：6 解释： 节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。 链表中没有其他孪生节点。 所以，链表的最大孪生和是 6 。

示例 2： 输入：head = [4, 2, 2, 3] 输出：7 解释： 链表中的孪生节点为：

• 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
• 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。 所以，最大孪生和为 max(7, 4) = 7 。

示例 3： 输入：head = [1, 100000] 输出：100001 解释： 链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

提示： 链表的节点数目是 [2, 10^5] 中的 偶数 。 1 <= Node.val <= 10^5

思路：思路是将链表中的值放入一个数组中，然后遍历数组，每次将数组中下标为 i 和 n - 1 - i 的元素加起来为，假设它们的和为 max ，每次进行判断取较大的 max 作为返回的最大孪生和；

		int pairSum(struct ListNode* head)
		{
		    //将链表中的值放入数组中
		    int arr[100000] = { 0 };
		    struct ListNode* cur = head;
		    int i = 0, n = 0, max = 0;
		    while (cur)
		    {
		        arr[n++] = cur->val;
		        cur = cur->next;
		    }
		
		    //遍历数组，每次将数组中下标为 i 和 n - 1 - i 的元素加起来为max，取较大的max
		    for (i = 0; i <= n / 2; i++)
		    {
		        max = arr[i] + arr[n - 1 - i] > max ? arr[i] + arr[n - 1 - i] : max;
		    }
		    return max;
		}