Leetcodehot100(链表篇)

链表

相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //la+c+lb 
        //lb+c+la 走完全程一定会相遇
        //返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 
        ListNode p=headA,q=headB;
        while(p!=q){
            p=p!=null?p.next:headB;
            q=q!=null?q.next:headA;
        }
        return p;
    }
}

反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

代码

/**
 * 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 reverseList(ListNode head) {
        ListNode dummy=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=dummy;
            dummy=cur;
            cur=next;
        }
        return dummy;
        
    }
}

回文链表

题目

给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。如果是，返回 true ；否则，返回 false 。

代码

/**
 * 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) {
         // 计算链表长度
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }

        if (len == 0) return false;

        if (len % 2 == 0) {
            // 链表长度为偶数
            int halfLen = len / 2;
            ListNode cur1 = head;
            ArrayList<Integer> firstHalf = new ArrayList<>();
            ArrayList<Integer> secondHalf = new ArrayList<>();

            for (int i = 0; i < halfLen; i++) {
                firstHalf.add(cur1.val);
                cur1 = cur1.next;
            }

            for (int i = halfLen; i < len; i++) {
                secondHalf.add(cur1.val);
                cur1 = cur1.next;
            }

            Collections.reverse(secondHalf);

            for (int i = 0; i < halfLen; i++) {
                if (!firstHalf.get(i).equals(secondHalf.get(i))) {
                    return false;
                }
            }
            return true;
        } else {
            // 链表长度为奇数
            int halfLen = len / 2;
            int middlePos = (len + 1) / 2;
            int count = 1;
            ListNode cur2 = head;
            ArrayList<Integer> firstHalf = new ArrayList<>();
            ArrayList<Integer> secondHalf = new ArrayList<>();

            for (int i = 0; i < halfLen; i++) {
                firstHalf.add(cur2.val);
                cur2 = cur2.next;
                count++;
                if (count == middlePos) {
                    cur2 = cur2.next;
                }
            }

            for (int i = halfLen + 1; i < len; i++) {
                secondHalf.add(cur2.val);
                cur2 = cur2.next;
            }

            Collections.reverse(secondHalf);

            for (int i = 0; i < halfLen; i++) {
                if (!firstHalf.get(i).equals(secondHalf.get(i))) {
                    return false;
                }
            }
            return true;
        }
    }
}

环形链表

题目

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针进行判断
        ListNode slow=head,fast=head;
        //快指针可以向后移动两步的话 让快慢指针移动
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast) return true;
        }
        return false;
     }
}

环形链表 II

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //返回链表开始入环的第一个节点
        //如果链表无环，则返回 null
        //链表如果有环的那个结点
        //快慢指针进行判断
        ListNode slow=head,fast=head;
        //快指针可以向后移动两步的话 让快慢指针移动
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                //说明存在环  找环的入口节点
                slow=head;
                while(slow!=fast){
                    slow=slow.next;
                    fast=fast.next;
                }
                return slow;//相遇结点即是环的入口结点
            }
        }
        return null;
    }
}

合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

代码

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 定义一个虚拟头结点
        ListNode dummy = new ListNode(-1);

        // 定义遍历的指针
        ListNode pre = dummy;

        while (l1 != null && l2 != null) {
            // 如果当前list1的节点值小于等于list2当前的节点值
            if (l1.val <= l2.val) {
                pre.next = l1;
                l1 = l1.next;
                pre = pre.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
                pre = pre.next;
            }
        }

        if (l1 != null) {
            pre.next = l1;
        }
        if (l2 != null) {
            pre.next = l2;
        }

        return dummy.next;
    }
}

两数相加

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

代码

/**
 * 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(0);//创建一个哑结点
        dummy.next=null;
        int carry=0;//表示进位
        ListNode cur=dummy;
        while(l1!=null||l2!=null||carry!=0){//有进位的话 需要继续循环
            int sum=0;
            if(l1!=null){
                sum+=l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                sum+=l2.val;
                l2=l2.next;
            }
            sum+=carry;//加上进位 第一个数是没有进位的 进位是给下一个数用的
            carry=sum/10;//更新进位
            cur.next=new ListNode(sum%10);
            cur=cur.next;

        }
        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 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return null;
        }
        //策略 将n-1 节点直接指向n+1
        int len=0;
        ListNode p=head;
        while(p!=null){
            len++;
            p=p.next;
        }
        // 特殊情况处理：如果要删除的是头结点
        if (len == n) {
            return head.next;
        }
        //也就是正数len-n+1个结点 cur指针移动到len-n即可
        ListNode dummy=new ListNode(0);//创建一个哑结点
        dummy.next=head;
        ListNode cur=dummy.next;
        int pos=len-n;
        while(cur!=null){//pos:3
            pos--;
            if(pos==0){
                cur.next=cur.next.next;
                break;
            }
            cur=cur.next;
        }
        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 swapPairs(ListNode head) {
        //给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
        //因为头结点改变 所以需要设置一个哑结点
        if(head==null||head.next==null) return head; 
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode cur=dummy.next;
        //处理链表至少有两个结点的情况
        //定义快慢指针
        ListNode slow=dummy.next;
        ListNode fast=dummy.next.next;

    }
}

K 个一组翻转链表

题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

代码

/**
 * 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 p=head;
        while(p!=null){ //这里头指针被改变了
            n++;
            p=p.next;
        }
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        //用于翻转链表
        ListNode p0=dummy;
        ListNode pre=null;
        ListNode cur=head;
        //k个一组
        for(;n>=k;n-=k){
            for(int i=0;i<k;i++){//遍历k次
                ListNode next=cur.next;
                cur.next=pre;
                pre=cur;
                cur=next;
            }
            //创建哨兵节点  用于下一次遍历
            ListNode nxt=p0.next;
            p0.next.next=cur;
            p0.next=pre;
            p0=nxt;
        }
        return dummy.next;
    }
   
}

随机链表的复制

题目

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。

代码

/*
// 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) {
        //定义一个hash表存储 原始结点与拷贝结点的映射关系
        Map<Node,Node> mp=new HashMap<>();
        for(Node cur=head;cur!=null;cur=cur.next){
            //每遍历到一个结点就创建一个拷贝结点 并创建映射关系
            mp.put(cur,new Node(cur.val));
        }
        //对边进行拷贝
        for(Node cur=head;cur!=null;cur=cur.next){
            if(cur.next!=null) mp.get(cur).next=mp.get(cur.next);
            if(cur.random!=null) mp.get(cur).random=mp.get(cur.random);
        }
        return mp.get(head);
    }
}

排序链表

题目

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

代码

/**
 * 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 sortList(ListNode head) {
        // 递归终止条件：如果链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 使用快慢指针找到链表的中间节点
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;      // 慢指针每次走一步
            fast = fast.next.next; // 快指针每次走两步
        }

        // 将链表从中间断开，分成左右两部分
        ListNode temp = slow.next; // temp 是右半部分的头节点
        slow.next = null;          // 将左半部分的尾节点指向 null

        // 递归排序左半部分和右半部分
        ListNode left = sortList(head);  // 排序左半部分
        ListNode right = sortList(temp); // 排序右半部分

        // 合并两个有序链表
        ListNode pre = new ListNode(0); // 创建一个虚拟头节点
        ListNode result = pre;         // result 用于保存合并后的链表头节点

        // 遍历两个链表，按顺序合并
        while (left != null && right != null) {
            if (left.val < right.val) {
                pre.next = left; // 将 left 节点连接到结果链表
                left = left.next; // 移动 left 指针
            } else {
                pre.next = right; // 将 right 节点连接到结果链表
                right = right.next; // 移动 right 指针
            }
            pre = pre.next; // 移动 pre 指针
        }

        // 处理剩余的节点（如果有）
        pre.next = left != null ? left : right;

        // 返回合并后的链表头节点
        return result.next;
    }
}

合并 K 个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

代码

/**
 * 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) {
        // 如果链表数组为空，直接返回 null
        if (lists.length == 0) {
            return null;
        }

        // 创建一个虚拟头节点，用于简化边界条件处理
        ListNode d = new ListNode(-1);
        // p 是合并后链表的尾指针，初始指向虚拟头节点
        ListNode p = d;

        // 创建一个最小堆（优先队列），用于存储所有链表的头节点
        // 堆的大小为链表的数量，比较规则是按节点的值升序排列
        PriorityQueue<ListNode> qu = new PriorityQueue<>(lists.length, (o1, o2) -> o1.val - o2.val);

        // 遍历链表数组，将所有非空链表的头节点加入堆中
        for (ListNode node : lists) {
            if (node != null) {
                qu.add(node);
            }
        }

        // 不断从堆中取出最小节点，连接到合并后的链表中
        while (!qu.isEmpty()) {
            // 取出堆中的最小节点
            ListNode node = qu.poll();
            // 将最小节点连接到合并后的链表中
            p.next = node;
            // 如果最小节点的下一个节点不为空，将其加入堆中
            if (node.next != null) {
                qu.add(node.next);
            }
            // 移动 p 指针，使其指向新的尾节点
            p = p.next;
        }

        // 返回合并后的链表头节点（虚拟头节点的下一个节点）
        return d.next;
    }
}

LRU 缓存

题目

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

代码

class LRUCache {
    // LRU (最近最少使用) 缓存 least recently used
    private final int capacity;//定义一个缓存容量
    private final Map<Integer,Integer> cache=new LinkedHashMap<>();//自带双向链表的哈希表

    public LRUCache(int capacity) {
        this.capacity=capacity;
    }
    
    public int get(int key) {
        Integer value=cache.remove(key);
        if(value!=null){
            cache.put(key,value);//把key移到链表末尾
            return value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(cache.remove(key)!=null){
            cache.put(key,value);
            return;
        }
        if(cache.size()==capacity){
            Integer oldestKey=cache.keySet().iterator().next();
            cache.remove(oldestKey);//然后移除
        }
        cache.put(key,value);
    }
}

/**
 * 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);
 */

后续内容持续更新~~~