[剑指 Offer 第 2 版第 18 题] “删除链表中重复的结点”做题记录

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

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

给定单向链表的一个节点指针，定义一个函数在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++ 代码：

第 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;
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/