跳到主要内容

链表

链表的核心操作在于指针遍历、虚节点 (Dummy Node) 的使用、以及快慢指针。

141. 环形链表 (Linked List Cycle)​

题目描述​

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。否则，返回 false 。

解题思路​

快慢指针 (Floyd 判圈算法)。

  1. slow 每次走一步，fast 每次走两步。
  2. 如果有环，fast 终会追上 slow（相等）。
  3. 如果 fast 走到空，则没环。

Java 代码实现​

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

2. 两数相加 (Add Two Numbers)​

题目描述​

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

解题思路​

累加进位模拟。

  1. 使用 dummy 节点。
  2. 维护 carry 进位。
  3. 循环 while (l1 != null || l2 != null || carry != 0)。

Java 代码实现​

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

21. 合并两个有序链表 (Merge Two Sorted Lists)​

题目描述​

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

解题思路​

双指针遍历 + 虚节点。 比较 l1 和 l2 的值，将较小者接到 curr.next，最后处理剩余部分。

Java 代码实现​

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

138. 随机链表的复制 (Copy List with Random Pointer)​

题目描述​

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有两个节点 X 和 Y ，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

解题思路​

拼接 + 拆分 (不用辅助 Map)。

  1. 在每个节点 N 后面插入复制节点 N'。
  2. 复制 random 指针：curr.next.random = (curr.random != null) ? curr.random.next : null。
  3. 拆分链表：将 N' 链路单独提出来。

Java 代码实现​

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        for (Node curr = head; curr != null; curr = curr.next.next) {
            Node node = new Node(curr.val);
            node.next = curr.next;
            curr.next = node;
        }
        for (Node curr = head; curr != null; curr = curr.next.next) {
            if (curr.random != null) curr.next.random = curr.random.next;
        }
        Node res = head.next;
        for (Node curr = head; curr != null; curr = curr.next) {
            Node node = curr.next;
            curr.next = node.next;
            if (node.next != null) node.next = node.next.next;
        }
        return res;
    }
}

92. 反转链表 II (Reverse Linked List II)​

题目描述​

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

解题思路​

原地头插法。

  1. 找到 left 的前驱节点 pre。
  2. 遍历 right - left 次，将 curr.next 节点通过头插法插入到 pre 后面。

Java 代码实现​

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0), pre = dummy;
        dummy.next = head;
        for (int i = 0; i < left - 1; i++) pre = pre.next;
        ListNode curr = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }
}

25. K 个一组翻转链表 (Reverse Nodes in k-Group)​

题目描述​

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解题思路​

分段递归或迭代反转。

  1. 找到当前段的第 k 个节点。如果不足 k 个，直接返回。
  2. 记录下一段的起点 nextHead。
  3. 反转当前 k 个节点。
  4. 将反转后的尾部（原头部）连接到对 nextHead 递归处理的结果。

Java 代码实现​

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }
        if (count < k) return head;
        ListNode newHead = reverse(head, curr);
        head.next = reverseKGroup(curr, k);
        return newHead;
    }
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode prev = null, curr = head;
        while (curr != tail) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

19. 删除链表的倒数第 N 个结点 (Remove Nth Node From End of List)​

题目描述​

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题思路​

快慢指针 (双指针)。

  1. fast 先走 n + 1 步。
  2. slow 和 fast 同时移动直到 fast 为空。
  3. slow 此时正好位于倒数第 n 个节点的前驱位置。
  4. 执行删除：slow.next = slow.next.next。

Java 代码实现​

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy, second = dummy;
        for (int i = 0; i <= n; i++) first = first.next;
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

82. 删除排序链表中的重复元素 II (Remove Duplicates from Sorted List II)​

题目描述​

给定一个已排序的链表的头 head ，删除所有含有重复数字的节点，只保留原始链表中 只出现一次 的数字。返回同样按分类排序的结果。

解题思路​

虚节点 + 双指针探测。

  1. 使用 dummy 节点处理头部重复的情况。
  2. 只要 curr.next 和 curr.next.next 存在且值相等，就用一个 while 循环跳过所有该值的节点。
  3. 否则，curr 移动到下一个位置。

Java 代码实现​

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        while (curr.next != null && curr.next.next != null) {
            if (curr.next.val == curr.next.next.val) {
                int val = curr.next.val;
                while (curr.next != null && curr.next.val == val) {
                    curr.next = curr.next.next;
                }
            } else {
                curr = curr.next;
            }
        }
        return dummy.next;
    }
}

61. 旋转链表 (Rotate List)​

题目描述​

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

解题思路​

成环与断开。

  1. 遍历链表得到长度 n，且将尾节点连向头节点形成环。
  2. 向后走 n - (k % n) - 1 步找到新链表的尾部。
  3. 断开环。

Java 代码实现​

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int n = 1;
        ListNode curr = head;
        while (curr.next != null) {
            curr = curr.next;
            n++;
        }
        curr.next = head; // 接成环
        for (int i = 0; i < n - (k % n) - 1; i++) head = head.next;
        ListNode newHead = head.next;
        head.next = null; // 断开
        return newHead;
    }
}

86. 分隔链表 (Partition List)​

题目描述​

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对顺序。

解题思路​

两条链表双拼。

  1. 创建两个虚节点 small 和 large。
  2. 遍历原链表，小于 x 的接到 small 后面，否则接到 large 后面。
  3. 最后将 small 的末尾连到 large 的开头，并确保 large 的末尾指向 null。

Java 代码实现​

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode sHead = new ListNode(0), lHead = new ListNode(0);
        ListNode s = sHead, l = lHead;
        while (head != null) {
            if (head.val < x) { s.next = head; s = s.next; }
            else { l.next = head; l = l.next; }
            head = head.next;
        }
        l.next = null;
        s.next = lHead.next;
        return sHead.next;
    }
}

146. LRU 缓存 (LRU Cache)​

题目描述​

请你设计并实现一个满足 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) 的平均时间复杂度运行。

解题思路​

哈希表 + 双向链表。

  1. 哈希表 Map<Integer, Node> 用于 O(1) 查找节点。
  2. 双向链表（带 head 和 tail 哨兵）用于 O(1) 更新节点位置：新访问的节点移动到 head.next，淘汰节点从 tail.pre 移除。

Java 代码实现​

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node() {}
        Node(int k, int v) { key = k; val = v; }
    }
    private Map<Integer, Node> cache = new HashMap<>();
    private int size, capacity;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new Node(); tail = new Node();
        head.next = tail; tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (++size > capacity) {
                Node last = removeTail();
                cache.remove(last.key);
                size--;
            }
        } else {
            node.val = value;
            moveToHead(node);
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}