美文网首页
《剑指 Offer (第 2 版)》第 18 题:删除链表中重复

《剑指 Offer (第 2 版)》第 18 题:删除链表中重复

作者: 李威威 | 来源:发表于2019-05-26 00:04 被阅读0次

    第 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++ 代码:

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

    相关文章

      网友评论

          本文标题:《剑指 Offer (第 2 版)》第 18 题:删除链表中重复

          本文链接:https://www.haomeiwen.com/subject/chtizqtx.html