删除链表结点

NO1. 删除链表倒数第 k个结点

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。要求：空间复杂度 \(O(1)\)，时间复杂度 \(O(n)\)

如果倒数第 k 个结点刚好是头结点，那头结点需要特殊处理。为了各个结点能等同操作，设置一个虚拟头结点。

寻找倒数第 k 个结点常使用“快慢双指针”来实现。

算法流程：

• step 1 ：在原头结点前面添加一个虚拟头结点；
• step 2 ：使用快慢指针找到倒数第 k+1 个结点（有了前驱结点，第 k 个结点才能删掉）；
• step 3 ：删除倒数第 k 个结点，返回头结点；

代码实现：

public class Solution {
    static class ListNode {
        int val;
        ListNode next = null;
    }
    
    public ListNode removeNthFromEnd (ListNode head, int k) {
        // 1. 添加一个虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 2. 使用快慢指针找到倒数第 k+1 个结点
        ListNode prev = getNode(dummy, n);
        // 3. 删除 倒数 第 k 个结点
        prev.next = prev.next.next;
        return dummy.next;
    }
    // 找到倒数第 k+1 个结点
    public ListNode getNode(ListNode newHead, int k) {
        ListNode slow = newHead, fast = newHead;
        for(int i = 0; i <= k; i++)		fast = fast.next;
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

复杂度分析：

• 时间复杂度：\(O(n)\)，其中 \(n\) 为链表长度；
• 空间复杂度：\(O(1)\)，无额外辅助空间使用；

NO2. 删除有序链表中重复元素Ⅰ

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。例如：给出的链表为1→1→2→3→3，返回1→2→3。

进阶：空间复杂度 O(1)，时间复杂度O(n)

对于重复元素，仅保留第一个，后面重复地直接跳过。

算法流程：

• step 1 ：特殊情况判断（空链表或仅有一个结点的链表）；
• step 2 ：使用两个工作指针，一个指向重复元素的第一个结点（若存在），另一个往后遍历去重；

每轮循环结束时 prev 始终都是 cur 的前驱。

代码实现：

public class Solution {
    
    static class ListNode {
        int val;
        ListNode next = null;
    }
    
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null)    return head;
        ListNode cur = head.next, prev = head;
        
        while(cur != null) {
            // 元素重复，要删掉 cur
            if(prev.val == cur.val) {
                prev.next = cur.next;
            } else {
                // 没重复的 prev 了，prev 指向 cur，对下一个值进行去重
                prev = cur;
            }
            cur = cur.next;
        }
    }
}

复杂度分析：

• 时间复杂度：\(O(n)\)，其中 \(n\) 为链表长度；
• 空间复杂度：\(O(1)\)，无额外辅助空间使用；

NO3. 删除有序链表中重复元素Ⅱ

跟上一题的区别就在于，上一题的所有元素都至少会保留一个，而本题中只要有重复，重复结点一个也不保留。

例如：1→2→3→3→4→4→5，返回1→2→5.

本题跟上题不同，如果头结点重复了，那头结点就得删除，为了方便操作，添加一个虚拟头结点。

算法流程：

• step 1 ：特殊情况判断（空链表或仅有一个结点的链表）；

• step 2 ：添加一个虚拟头结点，为了方便删除第一个结点；

• step 3 ：还是利用两个工作指针，每次就比较相邻两个元素是否相等，

  • 相等的话就跳过所有重复结点（一个不留）；
  • 不相等，prev 指针后移，去判断 prev 下一个元素是否有重复；

• step 4 ：返回虚拟头结点的 next；

代码实现：

    public ListNode deleteDuplicates (ListNode head) {
        // 口 -> 1 -> 1 -> 2 -> 3 -> 3
        if(head == null || head.next == null)    return head;
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        ListNode prev = dummy, cur = dummy.next;
        
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                // 相邻元素相等，跳过
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 上面while结束，cur指向有重复的最后一个元素，这一步实现跳过所有重复结点
                prev.next = cur.next;
            } else {
                // 相邻元素不相等，prev指针后移，指向cur
                prev = cur;
            }
            cur = cur.next;
        }
        return dummy.next;
    }

复杂度分析：

• 时间复杂度：\(O(n)\)，其中 \(n\) 为链表长度；
• 空间复杂度：\(O(1)\)，无额外辅助空间使用；

小结

删除链表类问题，通常使用双指针来操作，prev指针来得到待删结点的前驱，cur指针用于得到待删结点的后继，通过两工作指针就能解决链表删除问题。

此外，如果头结点可能被删除，那就要构造一个虚拟头结点，方便删除头结点。