跳到主要内容

链表算法练习

链表（Linked List）是常用的线性结构。主要考察指针的操作、虚拟头结点的使用、快慢指针、链表反转等核心技巧。

160. 相交链表 (Intersection of Two Linked Lists)​

题目描述​

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

解题思路​

使用双指针。 指针 A 走完 headA 后转向 headB，指针 B 走完 headB 后转向 headA。由于 a + c + b = b + c + a，如果相交，它们总会在相交点相遇。

Java 代码实现​

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
}

206. 反转链表 (Reverse Linked List)​

题目描述​

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

解题思路​

迭代法。维护 prev 和 curr 指针。逐位改变 curr.next 的指向。

Java 代码实现​

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

234. 回文链表 (Palindrome Linked List)​

题目描述​

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。

解题思路​

  1. 快慢指针寻找链表中点。
  2. 反转后半部分链表。
  3. 比较前半部分和反转后的后半部分。

Java 代码实现​

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next; slow = slow.next;
        }
        ListNode secondHead = reverse(slow.next);
        ListNode p1 = head, p2 = secondHead;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next; p2 = p2.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev; prev = curr; curr = next;
        }
        return prev;
    }
}

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

题目描述​

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

解题思路​

快慢指针（龟兔赛跑）。快指针每次走两步，慢指针走一步。如果有环，快指针必定会追上慢指针。

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;
    }
}

142. 环形链表 II (Linked List Cycle II)​

题目描述​

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题思路​

  1. 快慢指针判断是否有环。
  2. 记录相遇点。将一个指针重新设在 head，另一个留在相遇点。两个指针同时同步移动一步，再次相遇的位置即为入环点。

Java 代码实现​

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next; slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

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

题目描述​

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

解题思路​

使用虚拟头结点。 遍历两个链表，不断将较小的节点尾插到结果链表中。

Java 代码实现​

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

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

题目描述​

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。

解题思路​

从链表头开始模拟加法。注意处理进位。

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 val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = val1 + val2 + carry;
            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;
    }
}

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

题目描述​

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

解题思路​

使用快慢指针。 快指针先走 n 步。然后快慢指针同时同步移动。当快指针到结尾时，慢指针正好处于待删除节点的前驱。

Java 代码实现​

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

24. 两两交换链表中的节点 (Swap Nodes in Pairs)​

题目描述​

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解题思路​

使用虚拟头结点。每次取待处理的一对节点，执行指针重定向。

Java 代码实现​

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode temp = dummy;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummy.next;
    }
}

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

题目描述​

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

解题思路​

辅助函数 reverse(a, b) 反转 [a, b) 范围内的节点。递归处理后面的内容。

Java 代码实现​

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

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

题目描述​

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

解题思路​

  1. 在每个原节点后插入对应的新节点：1 -> 1' -> 2 -> 2' -> ...
  2. 处理新节点的 random 指针。
  3. 拆分链表复原原链表。

Java 代码实现​

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        for (Node p = head; p != null; p = p.next.next) {
            Node newNode = new Node(p.val);
            newNode.next = p.next; p.next = newNode;
        }
        for (Node p = head; p != null; p = p.next.next) {
            if (p.random != null) p.next.random = p.random.next;
        }
        Node dummy = new Node(0), curr = dummy, p = head;
        while (p != null) {
            curr.next = p.next; curr = curr.next;
            p.next = curr.next; p = p.next;
        }
        return dummy.next;
    }
}

148. 排序链表 (Sort List)​

题目描述​

给你链表的头结点 head ，请将其按 升序 排列并返回排序后的链表。要求达到 O(n log n) 时间复杂度。

解题思路​

使用归并排序。利用快慢指针寻找中心。递归地切割链表并合并有序链表。

Java 代码实现​

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
        }
        ListNode mid = slow.next; slow.next = null;
        return merge(sortList(head), sortList(mid));
    }
    private ListNode merge(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;
    }
}

23. 合并 K 个升序链表 (Merge K Sorted Lists)​

题目描述​

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

解题思路​

使用优先队列（最小堆）。将所有链表的头节点存入堆。每次弹出最小值并将其后继节点推入堆。

Java 代码实现​

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode node : lists) {
            if (node != null) pq.offer(node);
        }
        ListNode dummy = new ListNode(0), curr = dummy;
        while (!pq.isEmpty()) {
            ListNode minNode = pq.poll();
            curr.next = minNode; curr = curr.next;
            if (minNode.next != null) pq.offer(minNode.next);
        }
        return dummy.next;
    }
}

146. LRU 缓存 (LRU Cache)​

题目描述​

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

解题思路​

使用哈希表 + 双向链表。哈希表用于 O(1) 查找，双向链表记录顺序。 每次访问元素将其移到链表头。超出容量时，删除链表尾部的元素。

Java 代码实现​

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

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

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        moveAtHead(map.get(key));
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key); node.val = value;
            moveAtHead(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.prev.key); removeNode(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode); addAtHead(newNode);
        }
    }
    private void removeNode(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addAtHead(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
    private void moveAtHead(Node n) { removeNode(n); addAtHead(n); }
}