1. 首页
  2. 剑指offer经典面试题

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

[剑指 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++ 代码:

liwei201910112_1.png

第 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3267.html

« [剑指 Offer 第 2 版第 16 题] “数值的整数次方”做题记录
[剑指 Offer 第 2 版第 19 题] “正则表达式匹配”做题记录»

相关推荐

QR code