⭐ 题目日期：

字节实习 - 2024/10/24

🧗难度系数：

⭐️ ⭐️ ⭐

📝思路分析：

删除倒数第四个节点：

使用双指针法： - 定义两个指针 first 和 second，初始都指向链表的哑节点（dummy）。 - 先将 first 指针向前移动 n+1 步（这里 n=4），这样 first 和 second 之间相隔 n 个节点。 - 然后同时移动 first 和 second，直到 first 到达链表末尾。此时，second 的下一个节点就是需要删除的节点。 - 修改 second.next 指针，跳过需要删除的节点。

反转链表：

定义两个指针 prev 和 cur，初始时 prev 为 null，cur 为链表的头节点。遍历链表，在迭代过程中，将当前节点的 next 指针指向前一个节点，实现反转。最终，prev 指针将指向新的头节点。

💻代码：

Java

// 删除倒数第四个节点, 假定链表的长度大于4
public ListNode removeFourthFromEnd(ListNode head) {
    int n = 4; // 要删除的倒数第n个节点
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode first = dummyNode;
    ListNode second = dummyNode;

    // 将 first 指针向前移动 n+1 步
    for (int i = 0; i <= n; i++) {
        if (first != null) {
            first = first.next;
        }
    }

    // 同时移动 first 和 second，直到 first 到达末尾
    while (first != null) {
        first = first.next;
        second = second.next;
    }

    // 删除倒数第 n 个节点
    second.next = second.next.next;

    return reverseList(dummyNode.next);
}

// 反转链表
private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;

    while (cur != null) {
        ListNode next = cur.next; 
        cur.next = prev;              
        prev = cur;                   
        cur = next;               
    }

    return prev; 
}

🚵🏻复杂度分析：

时间复杂度: O(n), 遍历链表一遍，反转遍历链表一遍

空间复杂度: O(1)