数据结构与算法链表

　　链表
　　关于单链表，比较特殊，在面试中，要时刻注意时间复杂度和额外空间复杂度的问题
　　所以在笔试中，额外空间的应用无所谓，能做到即可，可以使用数组作为额外空间来使用
　　而在面试中要注意把额外空间复杂度降到最小，所以用克隆的方式来代替额外空间
　　这样子可以用不多的几个变量来确定关系，而位置的关系是通过克隆的位置关系来去确定的，这样的好处是让复杂度变低的同时还达到很好的效果桶排序
　　基数排序：分别按照个十百为先分别排序，然后再往上排序，对于每一位都是已经排好序，虽然不用进行比较，但是花费的空间和时间比较多基本稳定
　　在排完序之后还保持着排序前的基本序列，在班级中按照成绩排，相同的排序按照学号前后综合排序
　　在小样本的时候采用一种排序方式，大样本的时候采用另一种，让整体复杂度减小哈希表
　　无序的，但有序表的key是有序的
　　增删改查的复杂度都是常数，但是这个常数可能比较大
　　unordermap，unordertree
　　快慢指针求回文
　　也可以申请栈，将每个数遍历后都放进栈里面去，然后依次弹出，比较
　　可以采用快慢指针的方式，但是将头结点的下一位做慢指针，可以解决奇数和偶数问题
　　随机哈希表的设置
　　设置一个哈希表，将每个数的next和rand都放进哈希表里，第一次遍历老链表就是放进哈希表，第二次是根据哈希表里的next和rand，设置新链表的next和rand
　　直接插入克隆结点在当前结点后面，这样的话就不用在哈希表里设置next了，然后在遍历的时候设置一下边界，一对对遍历，存入rand即可，克隆节点的rand就是原本节点rand的克隆节点
　　有环链表
　　可以申请哈希表额外空间，记录每个遍历后的结点，第一次重复访问到的节点就就是环的开头
　　快慢指针：一开始都在head，慢指针一次走一步，快指针一次走两步，会在环里相遇，相遇后，快指针回到head，快慢指针同时走，都走一步，最终会在环的开始节点相遇无环链表
　　判断两条链表是否在同一地址，即最后节点是否相同，因为当两条单链表有相交时，相交部分一定是相同的，next指针是不会断的。
　　判断最后节点相同时即可判断出他们相交
　　让长链表先走x步，x为二者差值，然后二者同时走，一定会在相交节点相遇cur1n0？head1：head2谁长，谁的头是head1cur2cur1head1？head2：head1谁短，谁的头是cur2
　　重定位长短
　　如果是相同环，则把终止节点设置为俩链表入环节点，其余按照无环链表操作，如果不同环，从loop1开始，如果遇得到loop2，则是不同入环节点，返回谁都可以，但如果没有，则不相交
　　合并k个已排序链表
　　思路：多个指针，有限几个变量，采用merge方法，拆分出左右两组链表，然后进行合并，大化小step1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n2n2n2个链表和右边n2n2n2个链表。step2：继续不断递归划分，直到每部分链表数为1。step3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。classSolution｛public：ListNodeMerge2（ListNodephead1，ListNodephead2）｛if（phead1NULL）returnphead2；if（phead2NULL）returnphead1；ListNodeheadnewListNode（0）；ListNodecurhead；while（phead1phead2）｛if（phead1valphead2val）｛curnextphead2；phead2phead2next；｝else｛curnextphead1；phead1phead1next；｝curcurnext；｝if（phead1）curnextphead1；elsecurnextphead2；returnheadnext；｝ListNodepideMerge（vectorListNodelists，intleft，intright）｛if（leftright）returnNULL；elseif（leftright）returnlists〔left〕；intmid（leftright）2；returnMerge2（pideMerge（lists，left，mid），pideMerge（lists，mid1，right））；｝ListNodemergeKLists（vectorListNodelists）｛returnpideMerge（lists，0，lists。size（）1）；｝｝；链表中环的入口节点可以采用哈希表，放进去的节点遇到重复的第一个就是入环节点快慢指针：快指针走两步，慢指针走一步，当快慢指针相遇时，快指针返回起点，快慢指针一起走，都是走一步，再次相遇的节点就是入环节点classSolution｛public：ListNodeEntryNodeOfLoop（ListNodepHead）｛if（pHeadNULL）returnNULL；ListNodeslowpHead；ListNodefastpHead；while（fast！NULLfastnext！NULL）｛slowslownext；fastfastnextnext；if（slowfast）break；｝if（fastNULLfastnextNULL）returnNULL；fastpHead；while（fast！slow）｛fastfastnext；slowslownext；｝returnslow；｝｝；链表中倒数最后k个结点两次遍历的方法，先统计总长，然后nk次遍历找到可以快慢指针，快指针先走k步，然后和慢指针一起走classSolution｛public：ListNodeFindKthToTail（ListNodepHead，intk）｛writecodeherewhile（pHeadNULL）returnNULL；ListNodefastpHead；ListNodeslowpHead；for（inti0；ik；i）｛if（fastNULL）returnNULL；fastfastnext；｝while（fast！NULL）｛slowslownext；fastfastnext；｝returnslow；｝｝；删除链表的倒数第n个结点classSolution｛public：ListNoderemoveNthFromEnd（ListNodehead，intn）｛添加表ListNoderesnewListNode（1）；resnexthead；当前节点ListNodecurhead；前序节点ListNodepreres；ListNodefasthead；快指针先行n步while（n）fastfastnext；while（fast！NULL）｛fastfastnext；precur；curcurnext；｝删除该位置的节点prenextcurnext；返回去掉头returnresnext；｝｝；两个链表的第一个公共结点循环遍历两个链表，迟早会相遇publicListNodeFindFirstCommonNode（ListNodepHead1，ListNodepHead2）｛ListNodel1pHead1，l2pHead2；while（l1！l2）｛l1（l1null）？pHead2：l1。next；l2（l2null）？pHead1：l2。next；｝returnl1；｝额外空间的，所有都存进去，看是否有相同的双指针，先走差值步，然后同时遍历，第一个相同的就是公共结点
　　链表相加采用反转链表的方式classSolution｛public：ListNodereverselist（ListNodephead）｛if（pheadNULL）returnphead；ListNodecurphead；ListNodepreNULL；while（cur！NULL）｛ListNodetempcurnext；curnextpre；precur；curtemp；｝returnpre；｝ListNodeaddInList（ListNodehead1，ListNodehead2）｛writecodehereif（head1NULL）returnhead2；if（head2NULL）returnhead1；head1reverselist（head1）；head2reverselist（head2）；ListNoderesnewListNode（1）；ListNodeheadres；intcarry0；while（head1！NULLhead2！NULLcarry！0）｛intval1head1NULL？0：head1val；intval2head2NULL？0：head2val；inttempval1val2carry；carrytemp10；temp10；headnextnewListNode（temp）；headheadnext；if（head1！NULL）｛head1head1next；｝if（head2！NULL）｛head2head2next；｝｝returnreverselist（resnext）；｝｝；采用辅助空间的方式publicclassSolution｛publicListNodeaddInList（ListNodehead1，ListNodehead2）｛writecodehereif（head1null）returnhead2；if（head2null）｛returnhead1；｝使用两个辅助栈，利用栈先进后出，相当于反转了链表StackListNodestack1newStack（）；StackListNodestack2newStack（）；ListNodep1head1；ListNodep2head2；将两个链表的结点入栈while（p1！null）｛stack1。push（p1）；p1p1。next；｝while（p2！null）｛stack2。push（p2）；p2p2。next；｝进位inttmp0；创建新的链表头节点ListNodeheadnewListNode（1）；ListNodenHeadhead。next；while（！stack1。isEmpty（）！stack2。isEmpty（））｛val用来累加此时的数值（加数加数上一位的进位当前总的数值）intvaltmp；栈1不为空的时候，弹出结点并累加值if（！stack1。isEmpty（））｛valstack1。pop（）。val；｝栈2不为空的时候，弹出结点并累加值if（！stack2。isEmpty（））｛valstack2。pop（）。val；｝求出进位tmpval10；进位后剩下的数值即为当前节点的数值ListNodenodenewListNode（val10）；将结点插在头部node。nextnHead；nHeadnode；｝if（tmp0）｛头插ListNodenodenewListNode（tmp）；node。nextnHead；nHeadnode；｝returnnHead；｝｝
　　单链表的排序数组形式：创建一个数组，将链表内容放入，然后排序完恢复链表形式classSolution｛public：ListNodesortInList（ListNodehead）｛vectorintnums；ListNodephead；遍历链表，将节点值加入数组while（p！NULL）｛nums。pushback（pval）；ppnext；｝phead；对数组元素排序sort（nums。begin（），nums。end（））；遍历数组for（inti0；inums。size（）；i）｛将数组元素依次加入链表pvalnums〔i〕；ppnext；｝returnhead；｝｝；递归形式：每次分成两部分，然后将分割后的部分进行局部排序，最终达到整体有序classSolution｛public：ListNodemergelist（ListNodephead1，ListNodephead2）｛if（phead1NULL）returnphead2；if（phead2NULL）returnphead1；ListNodeheadnewListNode（0）；ListNodecurhead；while（phead1phead2）｛if（phead1valphead2val）｛curnextphead2；phead2phead2next；｝else｛curnextphead1；phead1phead1next；｝curcurnext；｝if（phead1）curnextphead1；elsecurnextphead2；returnheadnext；｝ListNodesortInList（ListNodehead）｛writecodehereif（headNULLheadnextNULL）returnhead；ListNodelefthead；ListNodemidheadnext；ListNoderightheadnextnext；while（right！NULLrightnext！NULL）｛leftleftnext；midmidnext；rightrightnextnext；｝左边指针指向左段的左右一个节点，从这里断开leftnextNULL；分成两段排序，合并排好序的两段returnmergelist（sortInList（head），sortInList（mid））；｝｝；
　　判断链表是否为回文结构存入数组的方式，然后将数组反转后对比存入数组的方式，得到数组长度，双指针分别从两端开始classSolution｛public：boolisPail（ListNodehead）｛vectorintnums；将链表元素取出一次放入数组while（head！NULL）｛nums。pushback（headval）；headheadnext；｝双指针指向首尾intleft0；intrightnums。size（）1；分别从首尾遍历，代表正序和逆序while（leftright）｛如果不一致就是不为回文if（nums〔left〕！nums〔right〕）returnfalse；left；right；｝returntrue；｝｝；快慢指针方式，记录到中间位置，然后反转后半部分，再对比（满足时间O（n），空间O（1））classSolution｛public：ListNodereverse（ListNodehead）｛ListNodepreNULL；while（head！NULL）｛ListNodenextheadnext；headnextpre；prehead；headnext；｝returnpre；｝boolisPail（ListNodehead）｛writecodehereListNodeslowheadnext；ListNodefasthead；while（fastnext！NULLfastnextnext！NULL）｛slowslownext；fastfastnextnext；｝fasthead；slowreverse（slow）；while（slow！NULL）｛if（fastval！slowval）returnfalse；slowslownext；fastfastnext；｝returntrue；｝｝；
　　链表的奇偶重排双指针的方式，将偶数的节点跳过，奇数的next直接指向下一个奇数，偶数则成为奇数的nextclassSolution｛public：ListNodeoddEvenList（ListNodehead）｛writecodehereif（headNULL）returnNULL；ListNodeevenheadnext；ListNodeoddhead；ListNodeevenoddeven；while（even！NULLevennext！NULL）｛oddnextevennext；oddoddnext；evennextoddnext；evenevennext；｝oddnextevenodd；returnhead；｝｝；
　　删除有序链表中重复的所有元素从0开始，不从1开始，这样的话可以从重复节点的上一个开始判断，每一次遇到重复前都可以判断出后面两个是否有重复元素classSolution｛public：ListNodedeleteDuplicates（ListNodehead）｛writecodehereif（headNULL）returnNULL；ListNoderesnewListNode（0）；resnexthead；ListNodecurres；while（curnext！NULLcurnextnext！NULL）｛if（curnextvalcurnextnextval）｛inttempcurnextval；while（curnext！NULLcurnextvaltemp）｛curnextcurnextnext；｝｝elsecurcurnext；｝returnresnext；｝｝；