第2天：链表算法 - 问题分析与Java实现

1. 问题分析

问题1：反转链表

问题描述

给定一个单链表的头节点 head，反转该链表并返回其头节点。

示例

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

2. 解决方案（多种方法）

方法1：迭代法（O(n))

思路：

• 遍历链表，同时反转每个节点的指针。
• 使用三个指针：prev、current 和 next 来跟踪节点并反转链表。

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev; // 返回新的头节点
}

优点：

• 时间复杂度：O(n)，n为链表的节点数量。
• 空间复杂度：O(1)，只使用了常量级别的额外空间。

方法2：递归法（O(n))

思路：

• 使用递归来反转剩余的链表，并在递归回溯时调整指针。

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode reversedList = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return reversedList;
}

优点：

• 时间复杂度：O(n)，递归遍历链表的每个节点。
• 空间复杂度：O(n)，由于递归栈的使用。

问题2：判断链表是否有环（弗洛伊德快慢指针法）

问题描述

给定一个链表，判断它是否有环。

示例

Input: head = [3,2,0,-4], pos = 1
Output: true
解释：链表中存在环，尾节点连接到索引为1的节点。

2. 解决方案（多种方法）

方法1：弗洛伊德快慢指针法（O(n))

思路：

• 使用两个指针，一个慢指针（slow）和一个快指针（fast）。
• 如果链表中有环，快指针会追上慢指针。

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

优点：

• 时间复杂度：O(n)，快慢指针各自遍历链表一次。
• 空间复杂度：O(1)，没有额外空间的使用。

方法2：HashSet法（O(n))

思路：

• 使用一个HashSet来存储已访问过的节点。如果遇到重复的节点，就说明有环。

import java.util.HashSet;

public boolean hasCycleHashSet(ListNode head) {
    HashSet<ListNode> visitedNodes = new HashSet<>();
    
    while (head != null) {
        if (visitedNodes.contains(head)) {
            return true;
        }
        visitedNodes.add(head);
        head = head.next;
    }
    return false;
}

优点：

• 时间复杂度：O(n)，遍历链表一次。
• 空间复杂度：O(n)，由于存储了链表节点的集合。

问题3：合并两个有序链表

问题描述

将两个有序链表合并为一个新的有序链表，并返回合并后的链表。

示例

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

2. 解决方案（多种方法）

方法1：迭代法（O(n))

思路：

• 同时遍历两个链表，比较每个节点的值，将较小的节点加入到新的链表中。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    if (l1 != null) {
        current.next = l1;
    } else {
        current.next = l2;
    }
    
    return dummy.next; // 返回合并后的链表
}

优点：

• 时间复杂度：O(n)，n为两个链表节点的总数。
• 空间复杂度：O(1)，仅使用指针来遍历链表。

方法2：递归法（O(n))

思路：

• 使用递归的方式合并两个链表，每次比较两个链表的头节点。

public ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    
    if (l1.val < l2.val) {
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;
    }
}

优点：

• 时间复杂度：O(n)，递归遍历两个链表。
• 空间复杂度：O(n)，递归栈的空间开销。

总结

🔥 掌握这些链表算法，提升你的面试能力，顺利应对大厂面试！ 🚀