算法日记 - Day8
两数相加
- 这是在计算两个数之和，因为是逆序，所以正好是从个位开始计算到十位到百位
- 需要考虑进位，进位最大是
1 - 如果
A链表中某个位置是空的，类似于B链表中同一个位置的值 +0+进位
使用指针，分别遍历两个链表同位置的数，计算两数以及前面的进位值的和，如果值 > 10，那么进位 1，如此循环。
classSolution{publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){ListNodehead=newListNode();ListNodecur=head;intcarry=0;while(l1!=null||l2!=null||carry!=0){intval=0;val+=l1==null?0:l1.val;val+=l2==null?0:l2.val;val+=carry;cur.next=newListNode(val%10);cur=cur.next;carry=val/10==0?0:1;l1=l1!=null?l1.next:null;l2=l2!=null?l2.next:null;}returnhead.next;}}因为最后
l1，l2都为null之后可能还有一个进位，所以还要再往前多算一次
删除链表中的节点
- 删除节点正常是需要它的前一个节点才可以，如果不行，只能伪删除，把后一个节点的值赋值到当前节点，把后一个节点删除，但是如果删除的是最后一个节点就不可以了，没办法删除，题目还说不是末尾节点，那答案就明显了
classSolution{publicvoiddeleteNode(ListNodenode){node.val=node.next.val;node.next=node.next.next;}}这个还给到中等难度…
删除链表的倒数第 N 个结点
- 在删除的时候，可以带上虚结点，这样第一个结点的删除也可以和其他位置的删除操作一致，不需要单独考虑了
- 要删除从前数第
n个位置的元素，那么就需要第n-1个位置的信息 - 使用左右指针，先让右指针走
n步，走到第n个结点，然后左右指针再同时走，当右指针到最后一个结点的时候，左指针就走到了倒数第n个位置的前一个元素。完美，然后执行删除操作就可以了
classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0,head);ListNodecur,pre;cur=pre=dummy;// cur 先走 n 步while(n--!=0){cur=cur.next;}// 一块走while(cur.next!=null){cur=cur.next;pre=pre.next;}pre.next=pre.next.next;// 删除，利用 Java 自己的垃圾回收，只要没人指向它就回收了returndummy.next;}}两两交换链表中的节点
如果能修改值交换可太方便了，嘿嘿
- 因为要交换节点，我们肯定是需要两个节点的前一个节点，所以这里加个虚结点更好统一操作
- 如果是奇数个节点，最后一个节点不交换
节点交换的示意图如下
classSolution{publicListNodeswapPairs(ListNodehead){ListNodedummy=newListNode(0,head);ListNodepre=dummy,cur=dummy.next;// cur 指向交换时的第一个结点，pre.next 指向 curwhile(cur!=null&&cur.next!=null){ListNodenxt=cur.next;pre.next=nxt;cur.next=nxt.next;nxt.next=cur;// 注意 cur 和 nxt 交换了，现在 nxt 在 cur 前面pre=cur;cur=cur.next;}returndummy.next;}}随机链表的复制
只考虑next还好，但是有 random 就不知道它指向谁了，有可能指向我们还没创建的节点，所以我的思路是把所有的节点先创建好，这样旧链表节点和新链表节点能够一一对应起来
classSolution{publicNodecopyRandomList(Nodehead){if(head==null)returnnull;Map<Node,Node>mp=newHashMap<>();Nodecur=head;// 先创建好新链表while(cur!=null){mp.put(cur,newNode(cur.val));cur=cur.next;}cur=head;// 依次赋值每个节点的 next 和 randomwhile(cur!=null){NodenewCur=mp.get(cur);// 可能指向 null，所以取不到设置默认值newCur.next=mp.getOrDefault(cur.next,null);newCur.random=mp.getOrDefault(cur.random,null);cur=cur.next;}returnmp.get(head);}}不用哈希表怎么做？这我自己想不到，我是抄灵神作业
例如链表 1→2→3，依次复制每个节点（创建新节点并复制 val 和 next），把新节点直接插到原节点的后面，形成一个交错链表：
1 → 1 ′ → 2 → 2 ′ → 3 → 3 ′ 1→1'→2→2'→3→3'1→1′→2→2′→3→3′
如此一来，原链表节点的下一个节点，就是其对应的新链表节点了！
然后遍历这个交错链表，假如节点 1 的 random 指向节点 3，那么就把新节点 1′
的 random 指向节点 3 的下一个节点 3′，这样就完成了对 random 指针的复制。最后，从交错链表中分离出 1′→2′→3′，即为深拷贝后的链表。
⚠注意：不能只删除节点 1,2,3，因为题目要求原链表的 next 不能修改。
classSolution{publicNodecopyRandomList(Nodehead){// 复制每个节点，把新节点直接插到原节点的后面for(Nodecur=head;cur!=null;cur=cur.next.next){cur.next=newNode(cur.val,cur.next);}// 遍历交错链表中的原链表节点for(Nodecur=head;cur!=null;cur=cur.next.next){if(cur.random!=null){// 要复制的 random 是 cur.random 的下一个节点cur.next.random=cur.random.next;}}// 把交错链表分离成两个链表Nodedummy=newNode(0);Nodetail=dummy;for(Nodecur=head;cur!=null;cur=cur.next,tail=tail.next){Nodecopy=cur.next;// 新节点tail.next=copy;// 把新节点插在 tail 的后面，构建新的链表cur.next=copy.next;// 恢复原节点的 next}returndummy.next;}}