算法日记 - Day8

两数相加这是在计算两个数之和因为是逆序所以正好是从个位开始计算到十位到百位需要考虑进位进位最大是1如果A链表中某个位置是空的类似于B链表中同一个位置的值 0进位使用指针分别遍历两个链表同位置的数计算两数以及前面的进位值的和如果值 10那么进位 1如此循环。classSolution{publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){ListNodeheadnewListNode();ListNodecurhead;intcarry0;while(l1!null||l2!null||carry!0){intval0;vall1null?0:l1.val;vall2null?0:l2.val;valcarry;cur.nextnewListNode(val%10);curcur.next;carryval/100?0:1;l1l1!null?l1.next:null;l2l2!null?l2.next:null;}returnhead.next;}}因为最后l1l2都为null之后可能还有一个进位所以还要再往前多算一次删除链表中的节点删除节点正常是需要它的前一个节点才可以如果不行只能伪删除把后一个节点的值赋值到当前节点把后一个节点删除但是如果删除的是最后一个节点就不可以了没办法删除题目还说不是末尾节点那答案就明显了classSolution{publicvoiddeleteNode(ListNodenode){node.valnode.next.val;node.nextnode.next.next;}}这个还给到中等难度…删除链表的倒数第 N 个结点在删除的时候可以带上虚结点这样第一个结点的删除也可以和其他位置的删除操作一致不需要单独考虑了要删除从前数第n个位置的元素那么就需要第n-1个位置的信息使用左右指针先让右指针走n步走到第n个结点然后左右指针再同时走当右指针到最后一个结点的时候左指针就走到了倒数第n个位置的前一个元素。完美然后执行删除操作就可以了classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummynewListNode(0,head);ListNodecur,pre;curpredummy;// cur 先走 n 步while(n--!0){curcur.next;}// 一块走while(cur.next!null){curcur.next;prepre.next;}pre.nextpre.next.next;// 删除利用 Java 自己的垃圾回收只要没人指向它就回收了returndummy.next;}}两两交换链表中的节点如果能修改值交换可太方便了嘿嘿因为要交换节点我们肯定是需要两个节点的前一个节点所以这里加个虚结点更好统一操作如果是奇数个节点最后一个节点不交换节点交换的示意图如下classSolution{publicListNodeswapPairs(ListNodehead){ListNodedummynewListNode(0,head);ListNodepredummy,curdummy.next;// cur 指向交换时的第一个结点pre.next 指向 curwhile(cur!nullcur.next!null){ListNodenxtcur.next;pre.nextnxt;cur.nextnxt.next;nxt.nextcur;// 注意 cur 和 nxt 交换了现在 nxt 在 cur 前面precur;curcur.next;}returndummy.next;}}随机链表的复制只考虑next还好但是有 random 就不知道它指向谁了有可能指向我们还没创建的节点所以我的思路是把所有的节点先创建好这样旧链表节点和新链表节点能够一一对应起来classSolution{publicNodecopyRandomList(Nodehead){if(headnull)returnnull;MapNode,NodempnewHashMap();Nodecurhead;// 先创建好新链表while(cur!null){mp.put(cur,newNode(cur.val));curcur.next;}curhead;// 依次赋值每个节点的 next 和 randomwhile(cur!null){NodenewCurmp.get(cur);// 可能指向 null所以取不到设置默认值newCur.nextmp.getOrDefault(cur.next,null);newCur.randommp.getOrDefault(cur.random,null);curcur.next;}returnmp.get(head);}}不用哈希表怎么做这我自己想不到我是抄灵神作业例如链表 1→2→3依次复制每个节点创建新节点并复制 val 和 next把新节点直接插到原节点的后面形成一个交错链表1 → 1 ′ → 2 → 2 ′ → 3 → 3 ′ 1→1→2→2→3→31→1′→2→2′→3→3′如此一来原链表节点的下一个节点就是其对应的新链表节点了然后遍历这个交错链表假如节点 1 的 random 指向节点 3那么就把新节点 1′的 random 指向节点 3 的下一个节点 3′这样就完成了对 random 指针的复制。最后从交错链表中分离出 1′→2′→3′即为深拷贝后的链表。⚠注意不能只删除节点 1,2,3因为题目要求原链表的 next 不能修改。classSolution{publicNodecopyRandomList(Nodehead){// 复制每个节点把新节点直接插到原节点的后面for(Nodecurhead;cur!null;curcur.next.next){cur.nextnewNode(cur.val,cur.next);}// 遍历交错链表中的原链表节点for(Nodecurhead;cur!null;curcur.next.next){if(cur.random!null){// 要复制的 random 是 cur.random 的下一个节点cur.next.randomcur.random.next;}}// 把交错链表分离成两个链表NodedummynewNode(0);Nodetaildummy;for(Nodecurhead;cur!null;curcur.next,tailtail.next){Nodecopycur.next;// 新节点tail.nextcopy;// 把新节点插在 tail 的后面构建新的链表cur.nextcopy.next;// 恢复原节点的 next}returndummy.next;}}