秋招突击——7/25——复习{两数相加、删除链表的倒数第N个节点、两两交换链表中的节点、LRU缓存}——新作{有塔游戏笔试——邻接集群的计算，最大收集点，国王收税}

引言

• 继续开始刷题，两道复习题，然后的就是晚上在更新的有塔笔试题了，继续加油！

复习

两数相加

• 题目连接

• 第一次练习连接

• 非空链表：不用处理特殊情况

• 逆序保存：最开始是个位，然后逐渐递增，由个位变成十位，百位等。

个人实现

• 主要分为三个步骤，分别是
  • 双链表同时遍历
  • 非空链表单独遍历
  • 处理剩下的冗余值

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   
        // define the head and redunt value 
        ListNode dummy = new ListNode(-1);
        int redunt = 0;
        ListNode temp = dummy;

        // traverse the list to judge 
        while(l1 != null && l2 != null){
   
            // cal the sum of num and redunt
            int sum = l1.val + l2.val + redunt;
            temp.next = new ListNode(sum % 10);
            redunt = sum / 10;

            // traverse next node
            temp = temp.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        // handle the not null list
        temp.next = (l1 == null? l2:l1);
        while(temp.next != null){
   
            int sum = temp.next.val + redunt;
            temp.next.val =  sum % 10;
            redunt = sum / 10;
            temp = temp.next;
        } 

        // handle the redunt
        if(redunt != 0){
   
            temp.next = new ListNode(redunt);
        }

        return dummy.next;
    }
} 

似乎我写的不够简洁，这道题我在字节面试的时候写过，我写完了，人家一脸嫌弃，感觉还是要背一下，看一下更加简洁的实现！

参考实现

• 这样写确实简单，这个题目应该背一下
• 记忆
  • 三合一，指针不空，增值非零
  • 增值累加，求余当前位，整除是进位。
    

最终修改如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
   
        // define the head and redunt value 
        ListNode dummy = new ListNode(-1),temp = dummy;
        int addNum = 0;

        // traverse the list to judge 
        while(l1 != null || l2 != null || addNum != 0){
   
            // cal the sum of num and redunt
            if(l1 != null) {
   
                addNum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
   
                addNum += l2.val;
                l2 = l2.next;
            }
            temp.next = new ListNode(addNum % 10);
            temp = temp.next;
            addNum /= 10;
        }

       
        return dummy.next;
    }
}

执行效率是一样的，但是代码更加简洁，记住就行了

删除链表的倒数第N个节点

• 题目链接

• 第一次学习连接

• 注意

• 链表一定存在节点，不会为空

个人实现

• 这个是很常规的地图，首先定位到倒数第n个节点，需要完整遍历一次链表，确定链表的长度，然后找到需要删除节点的前一个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {