单链表删除相关算法总结（5种题型）_实现单向链表删除算法。

目录

---

本文介绍单链表删除相关的常见算法。

1. 移除链表元素（力扣：203）
2. 删除链表中的节点（力扣：237）
3. 删除链表的倒数第N个节点（力扣：19）
4. 删除排序链表中的重复元素（力扣：83）
5. 删除排序链表中的重复元素 II（力扣：82）

算法实现

---

链表节点：

    public class ListNode{
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
1
2
3
4
5
6
7

1. 移除链表元素

题目

删除链表中等于给定值 val 的所有节点。

分析

1. 删除一个节点，我们首先要找到目标节点。
2. 然后，目标节点的上一个节点的next，指向目标节点的next节点，即可完成删除。
3. 然而head节点没有“上一个节点”，这时，我们需要新建一个哑节点，然后让它作为head节点的上一个节点。

哑节点

哑节点（dummy node）是初始值为NULL的节点，它可以起到避免处理头节点为空的边界问题的作用，减少代码执行异常的可能性。

哑节点的使用可以对代码起到简化作用，在删除节点，或者进行有序插入时，带有头部哑节点的链表可以简化代码的逻辑，我们的代码可以不用考虑第一个节点的特殊情况。

代码实现

    /**
     * 删除链表中等于val的所有节点 leetcode203
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val){
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode cur = pre;
        while (cur.next != null){
            if (cur.next.val == val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return pre.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2. 删除链表中的节点

题目

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

说明:

链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。

分析

这个题目输入参数只有一个，是将要删除的节点，所以题目可以理解为”删除指定的节点“。

删除当前节点，需要找到上一个节点，然后让上一个节点的next指向，当前节点的next节点即可。但是这是一个单链表，我们通过当前节点无法找到它的上一个节点。

所以，我们需要换个思路，将当前节点改为next节点，然后删除next节点也就变相的实现了删除当前节点了。

代码实现

    /**
     * 删除当前节点 leetcode 19
     * @param head
     */
    public void deleteNode(ListNode head) {
        ListNode next = head.next;
        head.val = next.val;
        head.next = next.next;
    }
1
2
3
4
5
6
7
8
9

3. 删除链表的倒数第N个节点

题目

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

分析

删除链表的倒数第N个节点，最简单的方法就是遍历链表，找到链表的长度，然后再找找倒数N个节点就非常简答了。但是这样会经过2次遍历。

我们换个思路：

1. 使用快慢指针（双指针），让快指针先走N-1个节点，然后快慢指针一起走，当快指针指向最后一个节点时，慢指针指向了倒数第N个节点。
2. 同时，我们可以使用哑节点来处理头节点的边界问题。

代码实现

    /**
     * 删除链表的倒数第N个节点  leetcode 19
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode quick = dummy;
        ListNode slow = dummy;
        for (int i = 0; i < n + 1; i++) {
            quick = quick.next;
        }
        while (quick != null) {
            quick = quick.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4. 删除排序链表中的重复元素

题目

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

分析

题目中的单链表是已排序的列表，所以，从链表头开始，依次对比节点值，如果相等，则删除即可。

代码实现

    /**
     * 83. 删除排序链表中的重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5. 删除排序链表中的重复元素 II

题目

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

分析

该题和上一题的区别是：要删除重复数字的所有节点。

思路1：可以使用上一题的思路，遍历整个链表，当节点中的值出现重复时，则删除重复的节点，例如节点3重复，则删除第一个之后所有重复的节点，最后删除当前节点即可。
思路2：遍历链表时，使用2个指针，第一个指针pre指向无重复节点的最右端，第二个指针cur指向当前节点，当前节点与后面节点值相等时，当前节点后移一位，直到找到不相等的值为止，这时让pre的next指向cur的next，就会把所有重复元素都删除掉了。

代码实现1

    /**
     * 82. 删除排序链表中的重复元素 II
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head, pre = dummy;
        boolean isDel = false;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
                isDel = true;
            } else {
                if (isDel) {
                    pre.next = cur.next;
                    cur = pre.next;
                    isDel = false;
                } else {
                    pre = cur;
                    cur = cur.next;
                }
            }
        }
        if (isDel) {
            pre.next = cur.next;
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

代码实现2

    /**
     * 82. 删除排序链表中的重复元素 II
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates1(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy.next, pre = dummy;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                while (cur != null && cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = pre.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24