编程导航会员会员
登录/注册

力扣刷题Hot100

昨晚的酒后劲有点大，一觉睡到2点..... 今天时间不多，补完hot 链表章节 明天二叉树树章节，然后再去刷刷牛客的。

  1. 2. 两数相加 - 力扣（LeetCode）
  2. 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
  3. 24. 两两交换链表中的节点 - 力扣（LeetCode）
  4. 25. K 个一组翻转链表 - 力扣（LeetCode）
  5. 138. 随机链表的复制 - 力扣（LeetCode）
  6. 148. 排序链表 - 力扣（LeetCode）
  7. 23. 合并 K 个升序链表 - 力扣（LeetCode）
  8. 146. LRU 缓存 - 力扣（LeetCode）

两数相加

双指针

▼
java
复制代码
/**
 * 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) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0){
            if (l1 != null){
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                carry += l2.val;
                l2 = l2.next;
            }
            cur = cur.next = new ListNode(carry % 10);
            carry /= 10;
        }
        return dummy.next;
    }
}

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

与寻找中间节点思路类似，先让fast提前走n布，再并起出发

▼
java
复制代码
/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        while (n-- > 0){
            fast = fast.next;
        }

        while (fast != null && fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

两两交换链表的节点

回忆一下，之前的反转链表是用到了几个指针，3个。

而这里需要两两反转，要用到4个指责。

为什么？因为上面是整个链表反转（或者说是一个一个反转），而下面是两个两个一组反转，于是需要需要多一个指针记录第二份node

▼
java
复制代码
/**
 * 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 swapPairs(ListNode head) {  
        ListNode dummy = new ListNode(0,head);
        ListNode node0 = dummy;
        ListNode node1 = dummy.next;

        while (node1 != null && node1.next != null){
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;

            node0.next = node2;
            node1.next = node3;
            node2.next = node1;

            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}

K个一组反转

类似链表反转+一组一组反转的思路。。。

▼
java
复制代码
/**
 * 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 reverseKGroup(ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while (cur != null){
           n ++;
           cur = cur.next; 
        }

        ListNode dummy = new ListNode(0,head);
        ListNode p0 = dummy;
        ListNode pre = null;
        cur = head;

        while (n - k >= 0){
            n -= k;
        
            for (int i = 0 ; i < k ; i++){
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }

            ListNode next = p0.next;
            next.next = cur;
            p0.next = pre;
            p0 = next;
        }
        return dummy.next;
    }
}

随机链表复制

有一个很巧妙的思路：138. 随机链表的复制 - 力扣（LeetCode）

▼
java
复制代码
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }

        Node cur = head;
        while (cur != null){
            cur.next = new Node(cur.val,cur.next);
            cur = cur.next.next;
        }
        cur =  head;
        while(cur != null && cur.next != null){
            if (cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        Node newHead = head.next;
        cur = head;
        while(cur != null && cur.next != null && cur.next.next != null){
            Node copy = cur.next;
            cur.next = copy.next;
            copy.next = copy.next.next;
            cur = cur.next;
        }
        cur.next = null;
        return newHead;
    }
}

排序链表

分治 + 合并两个有序链表

▼
java
复制代码
/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode mid = midd(head);
        ListNode pre = reverse(mid);
        while (pre != null){
            if (head.val != pre.val){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
        
    }


    private ListNode midd(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

}

合并K个升序链表

跟上面同样的思路

有一个堆的解法，但是我自己有点把握不住》。。。

▼
java
复制代码
/**
 * 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 mergeKLists(ListNode[] lists) {
        if (lists.length == 0){
            return null;
        }
        return mergeKLists(lists,0,lists.length-1);
    }

    private ListNode mergeKLists(ListNode[] lists , int l , int r){
            int n = r - l;
            if (r == l){
                return lists[r];
            } 
            ListNode left = mergeKLists(lists ,l , l + n / 2);
            ListNode right = mergeKLists(lists ,l + n / 2 + 1, r);
            return mergeTwoLists(left ,right);
    }
    
    private ListNode mergeTwoLists(ListNode list1 , ListNode list2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else{
                cur.next = list2; 
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 == null ? list2 : list1;
        return dummy.next;
    }

}

LRU 缓存

经典

▼
java
复制代码
class LRUCache {

    private static class Node{
        int key , value;
        Node pre , next;
        
        Node(int k , int v){
            key = k;
            value = v;
        }
    }


    private final int capacity;
    private Node dummy = new Node(0,0);
    private final Map<Integer,Node> m = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.pre = dummy;
        dummy.next = dummy;
    }
    
    public int get(int key) {
        Node node = getNode(key);
        return node != null ? node.value : -1;
    }
    
    public void put(int key, int value) {
        Node node = getNode(key);
        if (node != null){
            node.value = value;
            return;
        }
        node = new Node(key,value);
        m.put(key,node);
        pushFront(node);
        if (m.size() > capacity){
            Node endNode = dummy.pre;
            m.remove(endNode.key);
            remove(endNode);
        }
    }


    private Node getNode(int key){
        if (!m.containsKey(key)){
            return null;
        }
        Node node = m.get(key);
        remove(node);
        pushFront(node);
        return node;
    }

    private void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void pushFront(Node node){
        node.pre = dummy;
        node.next = dummy.next;
        node.pre.next = node;
        node.next.pre = node;
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
算法
学习打卡
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
quan
quan
等级
内容推荐
更多
Day 103✅ 今天做了：复习了多用户通信系统⏰ 明天计划：学习Java反射
1
Day 68时间19:00~ 22:00(3h)✅ 今天做了：Component注解、Mybatis配置、使用⏰ 明天计划：Lombok、Mapper映射、动态SQL📚 今日感悟：自动配置类DataSourceAutoConfiguration ，会读取properties文件，通过注解：@EnableConfigurationProperties(DataSourceProperties.cl
2
Day 19✅ 今天做了：MCP⏰ 明天计划：AI智能体构建📚 今日感悟：今天MCP问题有点多有点杂，明天找时间再捋一下。继续加油
1
Day 25✅ 今天做了：1、扇贝英语单词打卡2、英语听说读写、听力练习3、微信阅读15分钟4、编程导航学习⏰ 明天计划：待定📚 今日感悟：Keep going！
2
Day 104✅ 今天做了：学习了Java反射及快速入门⏰ 明天计划：继续学习Java反射
1
作者分享
更多
来上海啦，有没有租房的推荐哇，在徐汇区上班，酒店太贵了🤑。
4
好久没冒泡了，力扣热题100题分享也停更好久了。 但是也没浪费这段时间，这段时间总体是玩+面试+毕设。结果总体毕设差不多了，以及拿到了游族网络的实习offer，年后入职，java和kotlin，说是有转正机会。说实话还是有点犹豫的，因为后面有春招，我怕实习冲突，毕竟也不可能说把机会全压在这一个公司。然后又想去试试，毕竟也算是个国内比较大的游戏公司了，再刷个实习经历简历试试。 唉，这个就业形势，双非仔真的很难哦，我都开始做两手准备，测开，真的我这段时间也在看这方面的知识，我后面投大厂春招的话，真的会all in测开了碰碰运气了，java做第二手中厂或者游戏公司的准备。 我不喜欢说大话（社恐bushi）也没啥大目标，毕竟自己的实力和背景在这，所以我认为这也是我看的很开的原因，有份工作就不错了。。。说实话我还是这一届学院第一个有正儿八经的符合专业方向的应届生，然后总共也没几个有实习经历，有不少都去了学校合作的培训机构学游戏和嵌入式了，然后放弃秋招，直接春招，我看不懂。我玩的好的室友也是学游戏，然后让他年后来上海游族网络投递找我玩，哈哈哈。 不知不觉又写了怎么多，大家觉得我的年后安排合理吗（边实习边春招），大家可以分享一下自己的经历让我参考参考。😜 tips:上海租房好贵哦，公司在徐汇区，有推荐的嘛？
3
泛微网络深圳三面结束，挂了。。。。麻了，聊的挺好的啊，可能是我薪资要高了？？？不会吧，我问过朋友的，也有可能是我说我比较介意二开，更喜欢做新项目，太操蛋了，挂了，直接拉黑，没一点反馈。。。。 算了，反正也没什么意愿，因为做的业务不喜欢。 卧槽，成都的MOKA刚刚来电话了，周三面试，实习转正岗位（这又是什么时候投的？🤣） 转正9k * 15。 兄弟们这薪资怎么说？？？ 我先接面试试试我的技术水平吧。
2
力扣刷题Hot100
2
泛微网络实习面经
3
下载 APP