数据结构练级之路【小白白的初级单链表题目】

4.第四题（有关单链表和顺讯表的题目）
4.1有关顺序表的题目
4.1.1
这边我们可以先看两种题目类型的差别（IO类型和接口类型）……
例如：int* returnSize  --- 表示的是一个输出形参数，此时我就需要把我此时数组的大小告诉它（returnSize = 2;）,这个就是做接口型题目的一个注意点
并且此时的这个数组的大小是需要我们自己去malloc出来的（这个就是涉及到作用域了，所以不可以直接赋值），所以要进行malloc
int* arr =(int*)malloc(sizeof(int)*2);只有这样才可以很好的做一个接口型的OJ题
IO型就是什么都要自己去实现
题目（接口型实现）：移除元素
给你一个数组nums和一个值val，你需要在原地移除所有数值等于val的元素，并返回移除后数组的新长度
不使用额外的空间，你必须仅使用O（1）的空间并原地修改输入数组；元素的顺序可以改变，你不需要考虑数组中超出新长度后面的元素
接口型实现：
1.最好的解法
int removeElement(int* nums, int numsSize, int x)
{
  int i;
  int src = 0;
  int dest = 0;
  while (src < numsSize)
  {
    if (nums[src] != x)
    {
      nums[dest] = nums[src];//真的一定要牢记我的dest和src只是起下标的作用
      src++;
      dest++;
    }
    else
    {
      src++;
    }
  }
  /*return dest;*/
}
2.第二好的解法
 //int removeElement2(int* nums, int numsSize, int x)
{
  int i = 0;
  int tmp[20] = { 0 };
  for (i = 0; i < numsSize; i++)
  {
    if (nums[i] != x)
    {
      tmp[i] = nums[i];
      printf("%d ", tmp[i]);
    }
  }
}
//3.第三好的解法
int removeElement1(int* nums, int numsSize, int x)
{
  int i = 0;
  for (i = 0; i < numsSize; i++)
  {
    if (nums[i] == x)
    {
      nums[i] = nums[i + 1];
      numsSize--;
    }
    else
    {
      printf("%d ",nums[i]);
    }
  }
  return nums;
}
int main()
{
  int i;
  int arr[20] = { 1,2,2,2,3,4,4,4,1,6,5,3,2,5,6,7,3,7,10,2 };
  int arr[5] = { 1,2,3,4,5 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  removeElement(arr, sz, 2);
  printf("\n");
  removeElement1(arr, sz, 2);
  printf("\n");
  removeElement2(arr, sz, 4);
  printf("\n");
  return 0;
}
int removeElement(int* nums, int numsSize,int x)
{
  int src = 0;
  int dest = 0;
  while (src < numsSize)
  {
    if (nums[src] == x)
    {
      src++;
    }
    else
    {
      nums[dest] = nums[src];
      src++;
      dest++;//这个只是起下标的作用而已，所以可以随便你加，怎么加都可以
    }
  }
    printf("%d",nums[dest]);
}
题目：4.1.2（上面用接口实现，好像不是很好，这边我们用非接口实现）
题目：移除一个数组中的重复元素的个数 (用到了三个下标的使用来解决这个问题，是在用下标解决问题)（就是判断的逻辑）
总结：去重就是3下标问题（然后就是画图很重要）
int main()
{
  int i = 0, j = 1, dest = 0;
  int arr[20] = { 1,1,2,2,2,3,3,3,3,4,4,4,5,5,5,5,6,6,7,7 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  if (arr == 0)
  {
    return 0;
  }
  while (j < sz)//这步就是为了可以一直比较到最后一步，但是时间复杂度又是O（1）
  {
    if (arr[i] != arr[j])
    {
      arr[dest] = arr[i];
      i = j;
      j++;
      printf("%d \n", arr[dest]);
      dest++;//要小心这个dest会改变我的下标的位置（dest的本质就是一个下标而已）
    }
    else
    {
      //程序会来到这个地方就是说明此时的i和j是相等的，相等我就只要让j往后走就行了
      j++;
    }
  }
    //这个情况就是当我的倒数第一个和倒数第二个相等的时候，此时因为j已经大于循环，但是此时的i还没有赋值给dest，所以要拿来这边进行赋值
    arr[dest] = arr[i];
    printf("%d\n",arr[dest]);
    dest++;
  return dest;//此时的dest就是前面的数据的个数，是个数不是数，这边如果想要把数打出来就一定要用数组和循环
}
4.1.3 
题目：合并两个有序的数组（按从小到大） 此时的时间复杂度O（m+n） ,空间复杂度O（1）
思路：就是进行两个数组的比较，谁小谁就放在我们的空间大的数组中
int main()
{
  int i;
  int nums1[6] = { 1,2,3,0,0,0 };//就是把nums2的数据归并到nums1数组当中就行
  int nums2[3] = { 1,1,6 };
  int m = 3;//此时的这个m和n代表的是数组中的元素个数，0不算
  int n = 3;
  //方法一，重新开一个数组，把这些数字进行比较，然后把小的数字放到新的数组中，然后再把这个数组赋值给我的原来那个数组
  //方法二，不需要开一个新的数组，但是此时也不能从小开始比较（因为从小开始比较会导致数据被覆盖），所以我们此时从大开始比较就是一个最好的选择（就有点像是在逆序数组的时候，有时候不能从前向后，要从后向前）
  //有了方法现在就是要有几个注意点：首先做这中比较大小的题目（并且归并到已给同一个数组中的这种题目，一定要把从大的数字开始比较）
  int end1 = m - 1;
  int end2 = n - 1;
  int end = m + n - 1;//这三个下标一定要理解（是大下标到小下标）
  while (end1 >= 0 && end2 >= 0)//在while里面写的是（继续）真的条件，只要为假就结束
  {
    if (nums1[end1] >= nums2[end2])
    {
      //nums1[end--] = nums1[end--];写成这样也行，看你自己的水平
      nums1[end] = nums1[end1];
      end1--;
      end2--;
    }
    else
    {
      nums1[end] = nums2[end2];
      end1--;
      end2--;
    }
  }
  while (end2 >= 0)//此时的意思就是：如果数组空间小的此时里面还有数据没有比较完，此时就说明这里面的数据都是比较小的数，此时就可以直接放到空间大的数组中
  {
    nums1[end] = nums2[end2];//不敢不理解这个最后一步的把意思（就是当我的空间小的数组里面还有数据没有进行比较，此时就说明这些数据都是非常小的，此时又因为是从m和n下标开始进行的比较，所以此时就可以直接把数据放过去，因为此时end是6，m是3，n是3，都是从同一个下标开始的比较，千万不敢理解成了是从end下标开始进行的比较，只是把大的数据放到了end下标而已）
  }
  return 0;
}
链表的相关题目（虽然不会考察链表中的增删查改），但是考的都是增删查改的变形
4.2.1
题目：给你一个链表的头结点和一个整数num，请你删除链表中所有满足Node->data=num的结点，并返回新的头结点（就是像是删除一个数组中的指定的数）
思路：
方法一：遍历找num就行（但是是链表所以我们还要找到前一个，不然你把num删掉了，你就没有后面的数据了）
首先不要怕（我连删除任意位置的代码都随便写，这个不是更好写）
struct ListNode
{
  int data;
  struct ListNode* next;
};
//接口型的代码
struct ListNode* removeElements(struct ListNode* head, int num)
{
  struct ListNode* prev = NULL;
  struct ListNode* cur = head;//此时这个就可能导致头结点删不掉
  while (cur != NULL)
  {
    if (cur->data == num)
    {     //删除(但是要考虑到第一个数就是我要删除的数（此时就用一个头删就可以解决）)
      if (cur == head)//头删
      {
        head = cur->next;
        free(cur);
        cur = head;
      }
      else//中间删
      {
        prev->next = cur->next;
        free(cur);
        cur = NULL;
        cur = prev->next;//反正就是让cur一直去找，直到为空
      }
    }
    else
    {
      //迭代向后走
      prev = cur;
      cur = cur->next;
    }
  }
  return head;//此时就是可以不使用二级指针，因为此时我有一个返回值(struct ListNode*)这个类型的，此时不是void类型的
}
//4.2.2 
//调式链表的实现
int main()
{
  //有了这个鬼，以后链表的题目就可以不要再搞一个链表了，就可以直接这样写，调试的好帮手
  struct ListNode* plist1 = (struct ListNode*)malloc(sizeof(struct ListNode));
  struct ListNode* plist2 = (struct ListNode*)malloc(sizeof(struct ListNode));
  struct ListNode* plist3 = (struct ListNode*)malloc(sizeof(struct ListNode));
  struct ListNode* plist4 = (struct ListNode*)malloc(sizeof(struct ListNode));
  struct ListNode* plist5 = (struct ListNode*)malloc(sizeof(struct ListNode));
  struct ListNode* plist6 = (struct ListNode*)malloc(sizeof(struct ListNode));
  plist1->data = 7;
  plist2->data = 7;
  plist3->data = 7;
  plist4->data = 7;
  plist5->data = 7;
  plist6->data = 7;
  plist1->next = plist2;
  plist2->next = plist3;
  plist3->next = plist4;
  plist4->next = plist5;
  plist5->next = plist6;
  plist6->next = NULL;
  struct ListNode* head = removeElements(plist1, 6);
}
//此时来一个万能的链表模板（手动创建一个链表）
4.2.3
题目：给一个单链表的头结点head，请我反转链表，并返回反转后的链表（不画图容易写错，因为最后一步不好处理，所以做题目一定要多画图）
这个你怕个屁，不难
struct ListNode
{
  int data;
  struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head)
{
  这个题目可以用递归，但是不好（可以去研究一下）
  方法一、把箭头给换一下（就是调一个方向）（本质就是把结点中的地址给换一下，把存储后一个结点的地址变成存储前一个结点的地址）
  方法二、头插  思路：取原链表中的结点头插到新链表的新头结点当中
  听力大致的核心思路：（先自己干一下） 核心：图画清楚了，代码就是小事
  struct ListNode* node1 = NULL;//此时的n1代表的是NULL这个位置
  struct ListNode* node2 = head;//n2表示头结点的位置
  struct ListNode* node3 = head->next;
  struct ListNode* cur = head;
  while (cur != NULL)
  {
    node2->next = node1;
    node3->next = node2;
  }
  下面这种代码的注释更好，上面那个不怎么行
  if (head == NULL)
  {
    return NULL;
  }
  struct ListNode* prev = NULL;//此时的n1代表的是NULL这个位置
  struct ListNode* cur = head;//n2表示头结点的位置
  struct ListNode* next = head->next;
  while (cur != NULL)//此时就是cur为空这个代码就结束（然后此时的头结点就变成了prev，并且此时next会越界一个位置，所以要处理一下）
  {
    翻转（核心代码就这一句）
    cur->next = prev;
    迭代往后走（这步迭代一定要很清楚很明白，多看）
    prev = cur;
    cur = next;
    if (next != NULL)
    {
      next = next->next;//这步最后cur为空指针的时候next会越界,所以应该要放到一个if语句中进行判断一下
    }
  }
  return prev;//此时这个就是新的头结点了
}
方法二
struct ListNode* reverseList(struct ListNode* head)
{
  struct ListNode* cur = head;
  struct ListNode* newhead = NULL;
  while (cur != NULL)
  {
    头插(但是头插前就一定要先把上一个位置的地址先存起来)
    struct ListNode* next = cur->next;
    cur->next = newhead;
    newhead = cur;
    头插完就是迭代(但是一定要放在一个循环之中)
    cur = next;
  }
  return newhead;
}
4.2.4（快慢指针的用法）（快指针是慢指针的2倍走）
题目：给定一个头结点head的非空链表，返回链表的中间结点，如果有两个中间结点，则返回第二个中间结点
struct ListNode* middleNode(struct ListNode* head)
{
   反正大部分题目都是要遍历数据（遍历一次表示的是从头到尾表示一次，只要不到尾就不算是一次遍历，所以双指针很好用，因为大部分都是同时到达尾）
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  while (fast && fast->next)//这个结论就要去画图得到了，因为当奇数个时，fast是空，当偶数个时，fast->next才是空
  {
    只有当这两个条件都不为空，此时才向后走（条件都是至关重要的（大部分都是要通过画图得到））
    slow = slow->next;//这个就是表示一次走一步
    fast = fast->next->next;//这个就是表示一次走两步
  }
  return slow;//此时的slow就是表示中间的那个结点了（因为fast走的速度刚好是slow的两倍）
}
4.2.5 （千分尺法（反正就还是指针的用法），长短指针）
题目：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
struct ListNode* Node(struct ListNode* head,int k)
{
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  此时就是让fast先走k个，然后再一起走，等fast为空指针时，此时的slow就是我的倒数第k个了
  while (fast != NULL && k > 0)
  {
    fast = fast->next;
    k--;
  }
  while (fast)
  {
    slow = slow->next;
    fast = fast->next;
  }
  return slow;
}
4.2.6（无哨兵位的写法）
题目：将两个升序的链表合并为一个新的升序的链表并返回，新链表是通过给定的两个链表的所有的结点组成的
struct ListNode* Node(struct ListNode* list1, struct ListNode* list2)
{
  首先是除了while循环以外的条件
  if (list1 == NULL)
  {
    return list2;
  }
  if (list2 == NULL)
  {
    return list1;
  }
  这个题目就是涉及尾插和取结点和迭代遍历
  struct ListNode* head = NULL;
  struct ListNode* tail = NULL;
  while (list1 && list2)//有一个为空就结束（所以只有两个都不为空才会继续）
  {
    if (list1->data < list2->data)
    {
      此时就是把小的那个结点的数据拿去尾插
        尾插
      if (head == NULL)//但是防止一下第一次尾插时head为空
      {
        head = tail = list1;
      }
      else
      {
        tail->next = list1;
        /*tail = list1;*///这边两种都可以主要看你自己理解（但是还是要通过画图去理解）
        tail = tail->next;//这步就是为了让我的tail也可以动起来，这样tail就是我的尾了
      }
      list1 = list1->next;
    }
    else
    {
      尾插
      if (head == NULL)//但是防止一下第一次尾插时head为空
      {
        head = tail = list2;
      }
      else
      {
        tail->next = list2;
      /*  tail = list2;*/
        tail = tail->next;
      }
      list2 = list2->next;
    }
  }
  此时这个位置循环出来我们并不可以知道是谁为空了，所以这变要进行一个判断
  if (list1 != NULL)
  {
    tail->next = list1;
  }
  if (list2 != NULL);
  {
    tail->next = list2;
  }
  return head;
}
4.2.6.1（带哨兵位的写法）
struct ListNode* Node(struct ListNode* list1, struct ListNode* list2)
{
  if (list1 == NULL)
  {
    return list2;
  }
  if (list2 == NULL)
  {
    return list1;
  }
  struct ListNode* head = NULL;
  struct ListNode* tail = NULL;
  第一步来头
  head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//想要一个不存在的东西，就是自己创建，就是我malloc
  while (list1 && list2)
  {
    if (list1->data < list2->data)
    {
      tail->next = list1;
      tail = list1;
      list1 = list1->next;
    }
    else
    {
      tail->next = list2;
      tail = list2;
      list1 = list2->next;
    }
  }
  if (list1 != NULL)
  {
    tail->next = list1;
  }
  if (list2 != NULL);
  {
    tail->next = list2;
  }
  struct ListNode* plist = head->next;
  free(head);
  return plist;//这样写可以过，但是没有释放，所以要处理一下
}
4.2.7(较难)（链表的分割）
题目：现有一链表的头指针head，编写一段代码将所有的小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
思路1：假如可以不需要按原来顺序进行分割的话，那就是比大小然后进行头插和尾插就行了
思路2：
struct ListNode* partition(struct ListNode* phead, int x)
{
  struct ListNode* lessHead = NULL;
  struct ListNode* lessTail = NULL;
  struct ListNode* greaterHead = NULL;
  struct ListNode* greaterTail = NULL;
  开哨兵位的头结点，方便尾插
  lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
  lessTail->next = NULL;
  greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
  greaterTail->next = NULL;
  struct ListNode* cur = phead;//此时虽然可以用phead去迭代，但是不好，所以我们都是找一个替死鬼去走
  while (cur != NULL)//遍历
  {
    if (cur->data < x)//判断
    {
      有了哨兵位，这边我们就可以直接进行链接，不需要判断头结点是否为空了
      lessTail->next = cur;
      lessTail = cur;
    }
    else
    {
      greaterTail->next = cur;
      greaterHead = cur;
    }
    cur = cur->next;
  }
  遍历完之后就完成了我需要的步骤，此时就是把这两个链表给链接在一起，这样就可以完成任务了
  lessTail->next = greaterHead->next;
  greaterTail->next = NULL;//假如没有这句就会导致死循环（因为会头尾相连），关键所在，漏了就不好找了（叫我自己写，完……）
  struct LisNode* newHead = lessHead->next;
  free(lessHead);
  free(greaterHead);
  return newHead;
}
4.2.7(较难)（链表的回文结构）（用到了逆序和找中间结点）
题目：对于一个链表，请设计一个时间复杂度为O（n）空间复杂度为O（1）的算法，判断其是否为回文结构，给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构，保证链表的长度小于等于900
方法：就是先找中间位置，然后逆序中间结点后面的结点，最后进行比较
1.按照原理此时我就使用这个查找中间结点的函数
struct ListNode* middleNode(struct ListNode* head)
{
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  while (fast && fast->next)
  {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}
2.还有调用这个逆序链表的函数
struct ListNode* reverseList(struct ListNode* head)
{
  struct ListNode* cur = head;
  struct ListNode* newhead = NULL;
  while (cur != NULL)
  {
    struct ListNode* next = cur->next;
    cur->next = newhead;
    newhead = cur;
    cur = next;
  }
  return newhead;
}
3.此时就可以直接在我的判断回文的函数中调用这两个函数了，然后再进行一定的比较，这下就可以很好的完成我的判断是否是回文的代码了
bool chkPalindrome(struct ListNode* A)
{
  struct ListNode* mid = middleNode(A);
  struct ListNode* rHead = reverseList(mid);//意思就是我要逆置的mid之后的结点数据
  struct ListNode* curA = A;
  struct ListNode* curR = rHead;
  while (curA && curR)
  {
    if (curA->data != curR->data)                                             //一定要有图，一定要把过程给捋清楚
    { 
      return false;
    }
    else                                                      //这题的关键就是要画图把过程给捋清楚来 （到了后面代码不是问题，思路才是最重要的）
    {
      curA = curA->next;
      curR = curR->next;
    }
  }
  return true;
}
4.2.8(相交链表)(只能聚合，不能发散，Y字形，不是X字形)
题目：给你两个单链表的头结点headA，headB，请你找出并返回相交单链表的起始结点，如果两个链表没有交点就返回NULL;
思路一：（暴力求解法）遍历A链表，依次取A链表中的每一个结点，依次跟B链表中的的所有结点比较，如果有地址相同的结点，就是相交，第一个相同的交点
思路二：优化从O（N^2）到 O（N）
1.尾结点相同就是相交，否则就是不想交（因为如果这个链表是一个有交点的链表，那么它的尾结点就一定是相交的，因为链表只能是Y 字形的结构，不是X字形的结构）
 所以此时直接找尾，然后判一下就行了
2.求交点：此时就是想让这个代码是时间复杂度为O（2*N），就是双指针一起向后走（然后同一个位置的结点进行比较，如果相同就表示有交点）
但是这种原理的前提是两个链表要是相同的长度的，所以这变我们此时就要把链表的长度先给求出来（然后让更长的那个链表先走x步，走到最后跟较短的那个链表的长度一眼，然后开始比较）
3.头结点就是头结点，不能乱给它移动位置，所以都是用一个cur去迭代找尾
struct ListNode* getIntersectionNode(struct ListNdoe* headA, struct ListNode* headB)
{
  struct ListNode* tailA = headA;
  struct ListNode* tailB = headB;
  第一步：判断尾结点此时是否相等
  int lenA = 1;
  while (tailA->next)
  {
    lenA++;
    tailA = tailA->next;
  }
  int lenB = 1;
  while (tailB->next)
  {
    lenB++;
    tailB = tailB->next;
  }
  第二步，当尾结点不想交
  if (tailA != tailB)
  {
    return NULL;
  }
  此时就进行位置的调整（变到同一位置）（运用的就是有点像昨天的千分尺法）
  /*int gap = lenA > lenB ? lenA - lenB : lenB - lenA;*///这步判断可以用三目，也可以用绝对值函数
  int gap = abs(lenA - lenB);
  (下面这步就是经典的假设方法获得一个固定的变量)
  假设法第一步，定义两个变量
  struct ListNode* longList = headA;
  struct ListNode* shortList = headB;
  if (lenA < lenB)
  {
    longList = headB;
    shortList = headA;
  }
  while (gap--)
  {
    longList = longList->next;
  }
  while (longList != shortList)//此时的这步不敢去判断数据，我们此时要找的是结点的地址，不是结点中的数据，因为只有当结点的地址相同，此时才可以代表是交点，而不是数据相同，数据相同并不可以代表是交点
  {
    longList = longList->next;
    shortList = shortList->next;
  }
  return longList;
}
4.2.9（判断是否带环），区别4.2.9 区别带环并且返回入环时的第一个结点
bool hasCycle(struct ListNode* head)//有环就返回true无环就返回false
{
  struct ListNode* fast = head;
  struct ListNode* slow = head;
  while (fast && fast->next)//这个就是一次走两步，此时就会涉及到一个奇偶的问题，所以两个条件都要进行判断
  {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast)//这步就是表示我追击到了
    {
      return true;
    }
  }
  return false;
}
4.2.9.1（这个判断是否有环的题目代码写起来并不是很难）所以面试时一般会有别的问题
1.问题：问为什么slow走一步，fast走两步最后一定可以相遇；
1.解答：因为假如fast在追击slow的时候（此时的fast已经入环了，然后此时它们之间的距离是N），因为此时的fast每次都比slow多走一步，所以此时的距离就会从N到N-1，这样一直走下去，N肯定可以变成0，所以肯定可以找到
2.问题：问假如fast此时不走两步而是走n步，此时还一定可以找到吗？
2.解答：答案首先是：不可以；原因：假如此时的fast走的是3步，距离还是N，fast每次比slow多走2步，所以此时是N-2，N-4（所以就可以显然看出此时假如N是一个奇数就不能追到，只有当N是一个偶数的时候才可能追到），所以不一定可以追到
并且如果继续往下一圈走的时候，如果此时还是没有追到（那么此时的这个fast就不可能找到slow了）；因为：假如此时的N是一个奇数，然后此时就会导致fast在slow的前面（如果当我的fast在slow的前面时，此时的fast和slow的距离就发生的大改变，从小变成了最大，因为此时fast在前，所以距离就变成了环的长度-1（C-1））
所以假如C-1是一个奇数就会导致N是奇数（那么此时就又是那个道理，N是奇数就追不到），只有当C-1（N）是一个偶数时，才有可能追上，所以关键追上与追不上就是取决去（环的长度是奇数还是偶数），但是还要注意这边是有一个减1的
4.2.9.2 （较难且较经典）（有关链表带环的问题）（经典的引用了快慢指针的使用）（追击问题）
题目：给定一个链表，判断链表中是否有环,有环就返回入环点
意思：（没什么必要，图比较好理解）如果链表中有某一个结点，可以通过连续跟踪next指针再次到达，则链表中存在环，为了表示给定链表中的环，我们使用整数pos来表示链表尾链接到链表中的位置（索引从0开始），
如果pos的位置是-1.则在该链表中没有环，注意pos不作为参数进行传递，仅仅是为了标示链表的实际情况
思路：使用快慢指针（slow和fast都从头结点开始，slow一次走一步，fast一次走两步，不带环fast就会为空，带环fast就会追上我的slow）,但是如何求环的入口点呢？
 环的入口点的思路：一个指针从相遇点开始走，一个指针从链表头结点开始走，它们会在环的入口点相遇
实现：
4.2.10 （较难，大厂青睐）（复杂链表的复制）（复制带随机指针的链表）
题目很长，但是我们不要怕：给你一个长度为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指针
struct Node
{
  int data;
  struct Node* next;
  struct Node* random;//额外的指针
};
struct Node* capyRandomList(struct Node* head)
{
看到这个接口倒是很简单（就给了我一个头结点和一个返回值返回新的头结点的地址）
其实不好复制，所以我们现在就可以引进一个新的思路（巧）：1.第一步首先要把我的复制结点插入到原结点和下一个结点之间  2.第二步（最关键）处理复制结点的random（根据原结点的random，因为此时我的复制链表在原链表的后面一个位置，所以此时就可以利用原链表的random来控制复制链表的random）
3.把复制结点解下来链接成一个新链表，恢复原链表链接关系
实现：
  1.拷贝结点，插入原结点的后面
  struct Node* cur = head;
  while (cur)
  {
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->data = cur->data;
    插入结点
    copy->next = cur->next;
    cur->next = copy;
    cur = copy->next;//还是迭代
  }
  2.根据我的原结点，处理copy结点的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;//迭代
  }
  3.完成工作之后此时就可以把这个新的链表给解下来，就是拿下来，然后构成一个新的链表，然后返回新的头结点，此时我就表示成功的复制完了（同时恢复原链表）
  struct Node* copyHead = NULL;
  struct Node* copyTail = NULL;//此时就是尾插，为了可以不找尾，所以这边我们可以给一个尾指针（为什么单链表的时候不使用，是因为这个尾指针并不可以解决尾删等问题，所以这边刚好可以很好的使用）
  尾插
  cur = head;
  while (cur)
  {
    struct Node* copy = cur->next;
    struct Node* next = copy->next;
    if (copyTail == NULL)//不想写这步就可以给一个哨兵位，但是要malloc然后还要free也是有点麻烦
    {
      copyHead = copyTail = copy;
    }
    else
    {
      copyTail->next = copy;
      copyTail = copy;
    }
    这步就是为了让我的原链表给重新链接在一起
    cur = cur->next;//迭代
    cur = next;
  }
  return copyHead;
}