1.链表中的常用技巧1.1 画图在我们做算法题的时候画图是一个很有用的技巧当然对于链表这种数据也不例外在做算法题的时候我们能做到画图就一定要画图1.2 引入虚拟头节点也叫做哨兵位头节点我们可以自己再创建一个newhead结点让这个结点指向原先的头节点这样可以防止我们做题的时候有一种情况是我们的链表的头节点就是null的情况这个newhead的引入可以解决很多边界情况①便于处理边界情况②方便我们对链表进行操作1.3 不要吝啬空间、大胆定义变量在我们做算法题的时候我们经常会遇到上面这种在链表的两个结点中间插入一个结点cur的情况按理来说我们会使用上面这四步但是这样很容易出错这个时候我们可以考虑定义一个next的指针变量即让prev的next指针被命名为next的指针这样上面的四步就会变得简单起来上面的四步就变成了① cur-next next;② next-prev cur;③ prev-next cur;④ cur-prev prev;这四步的顺序是怎么样的也没有关系因为我们就不再害怕会丢了prev的next指针1.4 快慢双指针快慢双指针常被用于以下三种情况的题目题目1:判断链表有没有环判断链表有没有环最好的方法就是设置快慢指针让快指针一次走2步慢指针一次走1步这样的话如果这个链表没有环我们判断fast的next如果是nullptr的话则说明没有环如果有环则fast一定能追到slowclass Solution { public: bool hasCycle(ListNode *head) { ListNode * slow head; ListNode * fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; if(fast slow) { return true; } } return false; } };题目2找到链表中环的入口面对这道题我们想要找到环的入口就可以使用快慢指针和快慢指针的速度的不同进行数学关系的分析设 head到环的入口的距离 a; slow进入环之后行走的距离 b; 整个环的长度 L从slow和fast相遇的位置到环的入口 c;则 L bc; fast abnL; slow ab; 2slowfast ;则2a2b abbc; 最终我们推出来 ac!因此我们可以在slow和fast第一次相遇的时候定义一个新的结点ptr指向head,让ptr和slow每次向后走一步因为ac,所有在走了一定的步数之后ptr和slow相遇了相遇的位置刚好是环的入口class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode * slow head; ListNode * fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; if(slow fast) { ListNode * ptr head; while(ptr ! slow) { ptrptr-next; slowslow-next; } return ptr; } } return nullptr; } };题目3找到链表的第n个结点#include iostream class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(head nullptr) return nullptr; ListNode * m head; int count 0; while(m) { mm-next; count; } int end count-n; if(end 0) { ListNode * newhead head-next; delete head; return newhead; } ListNode * slow head; for(int i0;iend-1;i) { slow slow-next; } ListNode * toDelete slow-next; if(toDelete ! nullptr) { slow-next toDelete-next; delete toDelete; } return head; } };2.链表中的常用操作2.1创建一个新结点直接new 一个listNode 就可以了2.2 尾插定义一个变量tail指向链表的最后一个结点然后让tail的next指向这个要插入的新结点最后让这个新的结点成为新的tail结点2.3 头插在头插这种情况下我们之前说的虚拟头节点的效果就尤其明显了因为我们可以让想要被头插的这个结点的next指针指向虚拟头节点的next指针然后再让虚拟头节点的next指针指向这个要头插的结点逆序链表中就会用到头插这种情况class Solution { public: ListNode* reverseList(ListNode* head) { ListNode * newhead new ListNode(); newhead-next nullptr; ListNode * cur head; while(cur) { ListNode * next cur-next; ListNode *prev newhead-next; newhead-next cur; cur-next prev; curnext; } ListNode * result newhead-next; delete newhead; return result; } };
