合并两个有序链表

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按 非递减顺序 排列

解题思路

核心思想

1. 创建一个虚拟头节点(dummy head)简化操作

2. 使用双指针分别遍历两个链表

3. 每次比较两个指针所指节点的值，将较小的节点接入结果链表

4. 移动相应链表的指针和结果链表的指针

5. 最后返回虚拟头节点的下一个节点

代码执行流程分析

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 1. 创建虚拟头节点
    ListNode head = new ListNode();  // dummy node
    ListNode cur = head;             // 当前指针
    
    ListNode first = list1;
    ListNode second = list2;

    // 2. 遍历两个链表直到都为空
    while (first != null || second != null) {
        // 情况1：第一个链表已空，直接接第二个链表
        if (first == null) {
            cur.next = second;        // 连接当前节点
            second = second.next;     // 移动second指针
        } 
        // 情况2：第二个链表已空，直接接第一个链表
        else if (second == null) {
            cur.next = first;         // 连接当前节点
            first = first.next;       // 移动first指针
        } 
        // 情况3：second的值更小
        else if (first.val > second.val) {
            cur.next = second;        // 连接second的当前节点
            second = second.next;     // 移动second指针
        } 
        // 情况4：first的值更小或相等
        else {
            cur.next = first;         // 连接first的当前节点
            first = first.next;       // 移动first指针
        }
        // 移动结果链表的当前指针
        cur = cur.next;
    }
    
    // 3. 返回合并后的链表（跳过虚拟头节点）
    return head.next;
}
}

删除链表的倒数第 N 个结点

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

栈(Stack)数据结构

解题思路

使用栈(Stack)数据结构来解决"删除链表倒数第N个节点"的问题。栈是一种后进先出(LIFO)的数据结构，可以用来反转链表的顺序，通过将链表节点全部压入栈中，然后弹出N个节点，找到要删除的节点及其前驱节点

1. 第一次遍历：将链表所有节点依次压入栈

   • 例如链表 1->2->3->4->5，n=2

   • 栈中内容(从底到顶)：[1, 2, 3, 4, 5]

2. 弹出阶段：

   • 第一次弹出：5 (n=2 → n=1)

   • 第二次弹出：4 (n=1 → n=0) → 找到要删除的节点4

   • 查看栈是否为空：栈顶现在是3

   • 弹出3作为前驱节点，将3的next指向4的next(即5)

   • 结果链表：1->2->3->5

3. 特殊情况处理：

   • 如果要删除的是头节点(如n=链表长度)，栈弹出后为空

   • 直接返回头节点的next作为新头节点

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 1. 创建栈并遍历链表，将所有节点压入栈中
    Stack<ListNode> stack = new Stack();
    ListNode node = head;
    while (node != null) {
        stack.push(node);
        node = node.next;
    }
    
    // 2. 弹出栈顶元素，直到找到倒数第N个节点
    while (n > 0) {
        ListNode temp = stack.pop();
        if (--n == 0) {  // 当n减到0时，temp就是我们要删除的节点
            ListNode next = temp.next;
            
            // 3. 处理删除操作
            if (stack.isEmpty()) {
                // 如果栈为空，说明要删除的是头节点
                return next;
            } else {
                // 否则获取前驱节点并修改其next指针
                ListNode pre = stack.pop();
                pre.next = next;
            }
            break;
        }
    }
    return head;
}

快慢指针

解题思路

这个解法使用了快慢双指针技巧来高效地删除链表倒数第N个节点，无需使用额外空间（栈解法需要O(n)空间）。核心思想是：

1. 快指针先走N+1步：这样快慢指针之间保持N个节点的间隔

2. 同步移动双指针：当快指针到达链表末尾时，慢指针正好指向要删除节点的前驱节点

3. 删除目标节点：通过修改慢指针的next指针实现删除

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 创建虚拟头节点(dummy)
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    // 初始化快慢指针
    ListNode fast = dummy;
    ListNode slow = dummy;
    
    // 快指针先走n+1步
    while (n >= 0) {
        fast = fast.next;
        n--;
    }
    
    // 同步移动双指针直到快指针到达末尾
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除目标节点
    slow.next = slow.next.next;
    
    // 返回真正的头节点(可能已被删除)
    return dummy.next;
}