这周末爽刷力扣，写个博客回顾一下。
?之前很不适应力扣写函数的模式，不过好像写两道就习惯了。
707 设计链表?力扣
没什么可说的基础题，要注意的是链表是有头节点的。
------------------------------------------------------------------------
141 环形链表?力扣
这题就是快慢指针的应用了，当链表有环的时候，快指针一定可以追上慢指针。无环时，快指针会先到达链表尾部。
----------------------------------------------------------------------------
142 环形链表?力扣
也是快慢指针，由于要返回链表开始入环的第一个节点，所以稍微复杂一点，我们设未成环的节点长度为a，环节点的长度为b，这样当快指针追上慢指针时，我们设慢指针走了s，这样就是2s=s+nb，n是大于等于1的整数。于是就有s=nb，又因为a+nb还是入环的第一个节点，也就是说慢指针再走a就到达了入环的第一个节点，所以我们可以再加一个指针或者直接把快指针重新指向头节点，速度置为一，这样当他们再次相遇的时候一定位于入环的第一个节点。
------------------------------------------------------------------------------
160 相交链表?力扣
这题就是双指针，分别指向两个链表的头节点，当他们走到空指针时，分别置为另一个链表的头节点，当它们相等时返回其中一个即可。
这个可以想象为两个人，他们的速度的相同，并且由于链表相交，他们的起点可以视为相同，那么他们相遇的终点一定位于链表的相交点。想不通的话反过来想一想。如果链表不相交，那么他们最后相等的时候一定同时等于空指针。
（btw，颇有感触，当两个人走过完全相同的一段路，那么他们算不算、会不会相遇呢，如果他们还没有相遇，那么是不是注定不会相遇呢。）
-----------------------------------------------------------------------------
19 删除链表的倒数第N个节点??力扣
这题没什么难度，可以自己写一个函数用于获取链表的长度，然后对于头节点不好处理的情况，可以再头节点前面加上一个哑节点（只有指针域），这样的话对于这个新链表，原来的头节点就变成了一个普通的节点了。
-----------------------------------------------------------------------------------
2022/9/25
该睡觉了，就先写这么多了，明天接着写。
-----------------------------------------------------------------------------------------------------
206 反转链表?力扣
这题的话画图比较明白，感觉链表的题画图的话思路很清晰。
定义三个指针 cur,pre,end 名字也没什么特殊的意义。
cur指向当前待反转的节点
pre指向cur的下一个节点，用于保存。
end指向反转后的链表的头节点。
那么
while(cur!=NULL)
{
pre=cur->next; //保存原始链表
cur->next=end; //断开连接，建立新的连接
end=cur; //移位操作，让end指向反转后链表的新的头节点
cur=pre; //cur指向下一个待反转的节点
}最后返回end指针即可。
-----------------------------------------------------------------------------
203 移除链表元素?力扣
同样的思路，为了把头节点变得普通，新建了一个哑节点。
在遍历链表的时候，当遇到要删除的点时，应当删除，但不需要移动，应当是出现下一个不需要删除的数的时候，移动指针。可以避免出现连续需要删除节点出错的问题。
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode *cur=(struct ListNode *)malloc(sizeof(struct ListNode));
cur->next=head;
struct ListNode *temp=cur;
while(cur->next)
{
if(cur->next->val != val)
{
cur=cur->next;
}
else
{
cur->next =cur->next->next;
}
}
return temp->next;
}-----------------------------------------------------------------------------
328 奇偶链表?力扣
这题就是通过遍历链表，把链表分开为奇数链表和偶数链表，然后让奇数链表的尾节点连上偶数链表的头节点即可。
struct ListNode* oddEvenList(struct ListNode* head){
if(head == NULL || head->next == NULL)
return head;
struct ListNode *odd =head;
struct ListNode *even=head->next;
struct ListNode *evenhead=even;
while(even != NULL && even->next != NULL)//由于偶节点一定在奇数节点后面所以循环条件是这样
{
even=odd->next;
odd->next = even->next;
even->next =odd->next->next;
odd=odd->next;
even=even->next;
}
odd->next=evenhead;
return head;
}------------------------------------------------------------------------------
234 回文链表?力扣
这题我觉得好难，我觉得回文都挺难的。
由于是回文，那么我们会想到，用递归遍历到最后一个节点再回溯来实现反向遍历的思路。
但是还是有别的地方不好想。
struct ListNode *pre;
bool dfs(struct ListNode *cur)
{
if(cur != NULL)
{
if(!dfs(cur->next))//这一步是很巧妙的，既是递归又是出口，出口指的是一旦出现return false的情况那么就会一层层的向上return false,而第一次出现false的情况只能是出现了不匹配的情况
{
return false;
}
if(cur->val != pre->val)
{
return false;
}
pre=pre->next;//比较下一个
}
return true;
}
bool isPalindrome(struct ListNode* head){
pre=head;
return dfs(head);
}其实这种递归的做法还是有浪费的地方，也就是链表前半部分会重复比较一次。