day4刷题

1.两两交换链表中的节点题目/讲解//两两交换需要用到三个指针节点一个temp节点publicListNodeswapPairs(ListNodehead){if(headnull){returnnull;}//注意判空ListNodedummyNodenewListNode();dummyNode.nexthead;ListNodeoneNodenewListNode();ListNodetwoNodenewListNode();ListNodethreeNodenewListNode();oneNodedummyNode;twoNodehead;threeNodehead.next;//注意赋值准确ListNodetempNodenewListNode();while(threeNode!nulltwoNode!null){tempNodethreeNode.next;//一定要temponeNode.nextthreeNode;//尽量按顺序threeNode.nexttwoNode;twoNode.nexttempNode;oneNodetwoNode;//注意每次循环变化的取值twoNodetwoNode.next;if(twoNodenull){threeNodenull;}//注意判空else{threeNodetwoNode.next;}ListToArr.toArr(dummyNode.next);}returndummyNode.next;//注意返回值不要head}2删除链表的倒数第N个节点题目/讲解//已AC。快慢指针publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodefastNodenewListNode();ListNodeslowNodenewListNode();ListNodedummyNodenewListNode(0,head);fastNodedummyNode;slowNodedummyNode;for(inti0;in;i){fastNodefastNode.next;}while(fastNode.next!null){slowNodeslowNode.next;fastNodefastNode.next;}slowNode.nextslowNode.next.next;returndummyNode.next;//能用dunmmy优先用少数不能用比如从0添加反转。有dunnmy返回值一定用3.链表相交题目/讲解//已AC。注意从开始对齐还是从结尾对齐。publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){intlenA0;intlenB0;intlen0;ListNodetempNodenewListNode();ListNodecurAnewListNode();ListNodecurBnewListNode();curAheadA;curBheadB;while(curA!null){curAcurA.next;lenA;}while(curB!null){curBcurB.next;lenB;}if(lenAlenB){lenlenA-lenB;tempNodeheadA;headAheadB;headBtempNode;}else{lenlenB-lenA;}for(inti0;ilen;i){headBheadB.next;}while(headB!null){if(headAheadB){returnheadB;}else{headAheadA.next;headBheadB.next;}}returnnull;}4.环形链表II题目/讲解//已AC。1.判断是否有环2. 有环求相交点(速度k 2k)3.根据相交点求入环点公式2(xy) yxn(yz) - x zn为1与n为其他数代码一致x (n-1)(yz) z。publicListNodedetectCycle(ListNodehead){ListNodefastNodehead;ListNodeslowNodehead;while(fastNode!nullfastNode.next!null){slowNodeslowNode.next;fastNodefastNode.next.next;if(slowNodefastNode){slowNodehead;//注意初始化为headwhile(slowNode!fastNode){slowNodeslowNode.next;fastNodefastNode.next;}returnfastNode;}}returnnull;}