《剑指 Offer （第 2 版）》第 18 题：删除链表中重复

第 18-1 题：在 时间删除链表结点（多写几遍）

传送门：AcWing：在 O(1) 时间删除链表结点。

给定单向链表的一个节点指针，定义一个函数在 时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

样例：

输入：链表 1->4->6->8，删掉节点：第 2 个节点即 6（头节点为第 0 个节点）

输出：新链表 1->4->8

思路：待删除的结点是末尾结点的情况比较容易忽略，刚好题目中说“该节点一定不是尾节点”。

Python 代码：

# 28. 在O(1)时间删除链表结点
# 给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
#
# 假设链表一定存在，并且该节点一定不是尾节点。
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void
        """
        next = node.next
        node.val = next.val
        node.next = next.next
        next.next = None

C++ 代码：

image-20190108002212753

第 18-2 题：删除链表中重复的结点

同 LeetCode 第82 题。

传送门：AcWing：删除链表中重复的节点，牛客网 online judge 地址。

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例1：

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2：

输入：1->1->1->2->3

输出：2->3

思路：因为头结点可能被删，所以要设置一个虚拟头结点。

Python 写法：

class Solution(object):
    def deleteDuplication(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None

        dummy = ListNode(-1)
        dummy.next = head
        cur = dummy

        # 一下子要看两个，所以是
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                # 删除的起点至少是 cur.next.next
                del_node = cur.next.next

                while del_node.next and del_node.val == del_node.next.val:
                    del_node = del_node.next
                # 来到了一个新的结点，值不同

                cur.next = del_node.next
                del_node.next = None
            else:
                cur = cur.next

        return dummy.next

Java 代码：

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    public ListNode(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = arr[0];
        ListNode cur = this;
        for (int i = 1; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val + " -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = pHead;
        ListNode curNode = dummyNode;
        while (curNode.next != null && curNode.next.next != null) {
            ListNode next = curNode.next;
            ListNode nextNext = next.next;
            if (next.val == nextNext.val) {
                while (nextNext.next != null && nextNext.val == nextNext.next.val) {
                    nextNext = nextNext.next;
                }
                ListNode delNode = nextNext;
                curNode.next = delNode.next;
                delNode.next = null;
            } else {
                curNode = curNode.next;
            }
        }
        return dummyNode.next;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 3, 4, 4, 5};
        ListNode head = new ListNode(nums);
        System.out.println(head);

        Solution solution = new Solution();
        ListNode deleteDuplication = solution.deleteDuplication(head);
        System.out.println(deleteDuplication);
    }
}

LeetCode 第 82 题： 删除排序链表中的重复元素 II

传送门：82. 删除排序链表中的重复元素 II。

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

示例 1:

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

示例 2:

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

Java 代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
       if (head == null) {
            return null;
        }
        // 只要涉及头结点的操作，我们都设立虚拟头结点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode curNode = dummyNode;
        while (curNode.next != null && curNode.next.next != null) {
            // 如果接连两个结点的 val 相等，至少要把它们都删掉
            if (curNode.next.val == curNode.next.next.val) {
                // 要删除的起点至少应该是当前判断相同的结点的第 2 个
                ListNode delNode = curNode.next.next;
                // 如果后面还有相同的结点，delNode 后移一位，即 delNode 应该是指向相同的结点的最后一个
                while (delNode.next != null && delNode.next.val == delNode.val) {
                    delNode = delNode.next;
                }
                curNode.next = delNode.next;
                delNode.next = null;
            } else {
                curNode = curNode.next;
            }
        }
        return dummyNode.next; 
    }
}

LeetCode 第 83 题： 删除排序链表中的重复元素

传送门：83. 删除排序链表中的重复元素。

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

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

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

Java 代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode curNode = head;
        while (curNode != null && curNode.next != null) {
            if (curNode.val == curNode.next.val) {
                ListNode delNode = curNode.next;
                // 继续向前找，看看，还有没有可以删除的结点
                while (delNode.next != null && delNode.next.val == delNode.val) {
                    delNode = delNode.next;
                }
                // 穿针引线
                curNode.next = delNode.next;
                delNode.next = null;
            } else {
                curNode = curNode.next;
            }
        }
        return head;
    }
}