leetcode刷题日记：LCR 142. 训练计划 IV，876. 链表的中间结点

今天���两道题涉及到的知识点是双指针以及合并链表的一些技巧（我是使用的迭代法的，看了题解之后才搞明白，希望能给大家讲清楚）

1.LCR 142. 训练计划 IV

题目描述：

思路分析：

这个链表很特殊，它的顺序是升序的，已经给你排好了，现在要求是合并之后再按照升序进行重新组装。一开始的时候我想直接先用给出的这两个链表来操作，先对一个链表进行循环，把另外一个链表中的节点的值与其比较，然后插到中间。但是这样的思路的问题在于最后我们是要返回一个链表的头结点的，但是我们在遍历的时候，会将头结点向后移，即使用另外一个变量来存储原来链表的头结点，指针在进行操作的时候还是会把这个新变量一同进行变化（昨天的文章里面谈到了这件事情，可以戳一下这个链接：leetcode刷题日记&总结）所以这个想法不能实现。

于是在很长时间没有结果之后，我看了题解的思路。使用非递归的方法，思路是这样的：首先设置prehead结点，在真正的头结点之前；然后设置一个prev指针在遍历时紧随在l1（表1每次向后推进的节点）或者l2（和表2同理）之前。每次比较两个链表的当前节点的数值大小，谁小就把他连在prev后面，然后prev再向前推进一个，同时，小的那一方链表也向后推进一个；如此继续循环往复的比较，直到短的那一个链表先为空；这样之后，长的链表的多余部分由于是肯定比这个连接半成品中最大节点要大的，所以直接再把后面这段连到后面即可。我从中学到了以下几点技巧：

1.在涉及对链表本身进行操作（比如反转），或者是对两个链表进行操作（比如今天的合并），往往需要设置一个新的节点作为第三者来进行存储，返回这个新的链表。

2.本题中，头结点会发生变化，不好返回，所以可以采取设置prehead先头结点的方式，再返回时，返回prehead->next即可。

3.关于prev的作用：假如不设置，直接用l1，l2完成遍历的话，那么，假如l1是2,3，l2是1，4，5，那么先比较时先是l2的1连上prehead，然后l2来到4，4又比l1的2要大，所以这次应该是l1的2连上去，但是连在哪里呢？此时l2已经在4的位置，而2要和l2的1相连，谁来充当l2的1这个角色呢？所以这就体现出prev的作用了：帮助存储需要进行连接的节点。这是存储前驱，又得可能还要存储后继，也是这个思路，后面如果遇到了我会再讲。

4.其实感觉还是有点栈的味道，就是prev向前移的时候，就像入栈时候更新栈顶一样，更新是为了能有一个指针（栈顶）可以在每次找的时候都能让新节点与之相连。

代码实现

struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {    struct ListNode *prehead=malloc(sizeof(struct ListNode));    struct ListNode*prev=prehead;//注意，prev一开始是和prehead一样的    if(l1==NULL){        return l2;    }    else if(l2==NULL){        return l1;    }    else{        while(l1!=NULL&&l2!=NULL){   if((l1->val)val)){    prev->next=l1;    l1=l1->next;   }   else{       prev->next=l2;//连接       l2=l2->next;//向后移动l2   }prev=prev->next;//更新prev    }    if(l2){        prev->next=l2;//看哪个链表没有遍历完，就把他连到后面    }    if(l1){        prev->next=l1;    }    }        return prehead->next;}

2. 876. 链表的中间结点

题目描述

思路分析

 看到标签是双指针，我就想怎么样用，昨天刚刚用双指针解决了一个找倒数的问题，依靠的是快慢指针之间的距离差；今天这个先让用不了距离差，我突然灵光乍现，既然是中间结点，当快指针到末尾的时候，慢指针恰好走了快指针一半的路程，那我可以这样设定：让快指针先走两步，慢指针再走一步即可；于是设立一个标志flag记录快指针走的步数，当flag为2时，慢指针向前进一步，然后记得flag清零。当快指针到NULL时，慢指针自然就是中间节点。

代码实现

struct ListNode* middleNode(struct ListNode* head) {    int flag=0;    struct ListNode* fast=head;    struct ListNode*slow=head;    while(fast){       fast=fast->next;       flag++;       if(flag==2){           slow=slow->next;           flag=0;       }}   return slow;    }

总结一下，还是对prev这种设置标志来进行连接的方法不熟，双指针的应用还要更多见识。

最后，感谢大家能不能给个一键三连哟~~~