面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "手写反转链表" "检测链表环" "合并有序链表"

预计阅读时间：35分钟

🔗 链表基础结构

链表节点定义

/**
 * 链表节点定义
 */
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; }
}

/**
 * 双向链表节点
 */
public class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    
    DoublyListNode() {}
    DoublyListNode(int val) { this.val = val; }
}

🔄 反转链表系列

基础反转操作

/**
 * 链表反转经典问题
 */
public class LinkedListReverse {
    
    /**
     * 反转链表
     * LeetCode 206: Reverse Linked List
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        
        return prev;
    }
    
    /**
     * 递归方式反转链表
     */
    public ListNode reverseListRecursive(ListNode head) {
        // 递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转后面的链表
        ListNode newHead = reverseListRecursive(head.next);
        
        // 反转当前连接
        head.next.next = head;
        head.next = null;
        
        return newHead;
    }
    
    /**
     * 反转链表II - 反转指定区间
     * LeetCode 92: Reverse Linked List II
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || left == right) return head;
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        // 找到反转区间的前一个节点
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        
        // 反转区间内的节点
        ListNode current = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode nextNode = current.next;
            current.next = nextNode.next;
            nextNode.next = prev.next;
            prev.next = nextNode;
        }
        
        return dummy.next;
    }
    
    /**
     * K个一组翻转链表
     * LeetCode 25: Reverse Nodes in k-Group
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        // 检查剩余节点是否足够k个
        ListNode current = head;
        int count = 0;
        while (current != null && count < k) {
            current = current.next;
            count++;
        }
        
        if (count == k) {
            // 递归处理后续节点
            current = reverseKGroup(current, k);
            
            // 反转当前k个节点
            while (count > 0) {
                ListNode nextTemp = head.next;
                head.next = current;
                current = head;
                head = nextTemp;
                count--;
            }
            head = current;
        }
        
        return head;
    }
}

🔍 链表环检测

环检测算法

/**
 * 链表环检测相关问题
 */
public class LinkedListCycle {
    
    /**
     * 环形链表检测
     * LeetCode 141: Linked List Cycle
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return true;
    }
    
    /**
     * 环形链表II - 返回环的起始节点
     * LeetCode 142: Linked List Cycle II
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // 第一次相遇：检测是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        
        if (fast == null || fast.next == null) return null;
        
        // 第二次相遇：找到环的起始节点
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
    
    /**
     * 环形链表的长度
     */
    public int cycleLength(ListNode head) {
        if (head == null || head.next == null) return 0;
        
        ListNode slow = head;
        ListNode fast = head;
        
        // 检测环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }
        
        if (fast == null || fast.next == null) return 0;
        
        // 计算环的长度
        int length = 1;
        fast = fast.next;
        while (slow != fast) {
            fast = fast.next;
            length++;
        }
        
        return length;
    }
    
    /**
     * 快乐数（使用链表环检测思想）
     * LeetCode 202: Happy Number
     */
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        
        return fast == 1;
    }
    
    private int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
}

🔗 合并有序链表

合并操作

/**
 * 链表合并相关问题
 */
public class LinkedListMerge {
    
    /**
     * 合并两个有序链表
     * LeetCode 21: