随机链表的复制
题目
思路：
思路：
①一个结点一个节点去拷贝，当拷贝了第一个节点的时候，把原节点与拷贝节点连接起来，直接到所有的节点拷贝完毕，这样做的目的是为下一步处理 random 指针做准备
② 处理random
③处理整个链表，还原原链表，连接复制的链表，返回头结点
详解步骤 ：
①一个结点一个节点去拷贝，当拷贝了第一个节点的时候，把原节点与拷贝节点连接起来，直接到所有的节点拷贝完毕，这样做的目的是为下一步处理 random 指针做准备
② 处理random，cur需要不断跌代，cur->next 则为 copyLsit(复制出来的结点)，观察可以发现，当cur->random->next 即为 copyList->random
③处理整个链表，还原原链表，连接复制的链表，返回头结点
完整代码：
struct Node* copyRandomList(struct Node* head)
{
if(head == NULL)
{
return NULL;
}
// 1，复制节点
struct Node* cur = head;
while(cur)
{
struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));
if(copyNode == NULL)
{
return NULL;
}
copyNode->next = NULL;
copyNode->random = NULL;
//连接复制的节点
struct Node* next = cur->next;
copyNode->val = cur->val;
cur->next = copyNode;
copyNode->next = next;
cur = next;
}
//处理random
cur = head;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = cur->next->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = next;
}
//处理整个链表,还原链表，返回复制链表的头节点
cur = head;
struct Node* copyHead = cur->next; //最后需要返回复杂链表的头
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
cur->next = next;
if(next)
copy->next = next->next;
cur = next;
}
return copyHead;
}排序链表
题目
思路
需用到这个题目：合并两个有序链表
在有归并排序的基础写这个题目就会轻松一点，因为这个题目和归并排序的非递归写法有点类似
先回忆一下归并排序的思想，归并排序是把一段无序的数据一个一个递归出去，然后把一个一个数据当成有序的，再合并，合成2个数后有序了，接下来2个合并，合并成4个数有序，再4个4个合并，以此类推，不断合并
①计算链表的个数，用于控制每一层合并的间距
②创建一个虚拟头节点(带哨兵位的头节点)，用于记录每组已经完成归并的链表
③分割链表，找每组的左右子链表进行合并有序链表
详细步骤：
①计算链表的个数，用于控制每一层合并的间距
②创建一个虚拟头节点(带哨兵位的头节点)，用于记录每组已经完成归并的链表
当 gap == 1 的时候，表示数据个数是一个，
我们需要合并 4 2 为一组合并，14 5 、10 15、 3 7 各为一组合并
创建 prev 指向虚拟头结点，cur 指向真正链表的头
prev用于记录每组链表中完成了合并有序链表的操作，cur用于找需要合并的子链表
head1表示左子链表，head2表示右子链表，在找左子链表的过程中，我们知道gap是会变化的，也就是说子链表的节点个数就是gap的值 (最后末尾可能会存在多一个或者少一个的情况，或者右子链表根本没有)
这只是gap == 1的情况下，gap第一次是 1，第二次是 2，第三次是 4，所以控制间距是 gap * = 2
③分割链表，找每组的左右子链表进行合并有序链表
如图所示：这只是gap == 1的情形，当 gap 不断变化的时候，原理都是一样的(建议自己画图动手理解)
边界的控制
完整代码
struct ListNode* MergerTwoLists(struct ListNode* list1,struct ListNode* list2)
{
struct ListNode* l1 = list1;
struct ListNode* l2 = list2;
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
struct ListNode* head = NULL, *tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while(l1 && l2)
{
if(l1->val < l2->val)
{
tail->next = l1;
l1 = l1->next;
}else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if(l1)
{
tail->next = l1;
}
if(l2)
{
tail->next = l2;
}
struct ListNode* reallyHead = head->next;
free(head);
return reallyHead;
}
struct ListNode* sortList(struct ListNode* head)
{
//计算排序链表的个数
int Length = 0;
struct ListNode* node = head;
while(node)
{
++Length;
node = node->next;
}
//创建虚拟头结点(带哨兵位的头结点)
//每组归并都是从头开始，最后用于返回头结点
struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
if(dummyHead == NULL)
return NULL;
dummyHead->next = head;
//分割区间
for(int gap = 1; gap < Length; gap *= 2)
{
struct ListNode* prev = dummyHead;
struct ListNode* cur = prev->next;
//找两个链表的头
while(cur)
{
//找了头还需要确定左子链表的末尾，断开联系，挪动cur的位置，先确定头再确定右子链表的末尾断开联系，保存下一个，让cur不断往后走，归并，
//归并完之后让 prev 不断走，合并完不需要合并，cur不断向后走
struct ListNode* head1 = cur;
for(int i = 1; i < gap && cur->next; ++i) //左子链表的确定，如果下一个结点为NULL说明到了末尾，没有右子链表
{
cur = cur->next;
}
struct ListNode* head2 = cur->next; // 如果head2 == NULL,不进人下面的for循环
cur->next = NULL; //确定了第一个左子链表
//确定右子链表
cur = head2; // cur 跟上
for(int i = 1; i < gap && cur && cur->next; ++i )
{
cur = cur->next;
}
//gap为 1的时候里面的一小部分，断开右子链表的联系
struct ListNode* next = NULL;
if(cur)
{
next = cur->next;
cur->next = NULL;
}
//这样两个左右子链表寻找完毕，接下来就需要合并有序链表了
struct ListNode* Mergerd = MergerTwoLists(head1,head2);
prev->next = Mergerd;
while(prev->next) // prev 找合并之后链表的尾
{
prev = prev->next;
}
cur = next; // cur继续更新
}
}
struct ListNode* reallyHead = dummyHead->next;
free(dummyHead);
return reallyHead;
}