美文网首页剑指offer最优解Java版
剑指offer最优解Java版-删除链表中重复的结点

剑指offer最优解Java版-删除链表中重复的结点

作者: 全菜工程师小辉 | 来源:发表于2019-07-13 10:17 被阅读4次

    题目描述

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

    解决方法

    两个阶段:

    1. 让快慢指针一起走,直到两个相遇。
    2. 假设从起点到环入口处距离为m,慢指针从环入口处继续走x距离,与快指针相遇。则将两个指针速度都变成每次一格,然后A指针从相遇点继续出发,B指针从起点开始出发。当他们再次相遇的时候,所处位置正好是环的入口。

    设C为环周长,第一次相遇,快指针已经走了,可以得到:
    m+x%c = m+(2x+m)%c
    进而获得:
    (x+m)%c=0

    所以,才会有第二阶段,让两个指针同时出发,当B指针走了m的时候,正好是环入口,也正好与A指针相遇。

    public static ListNode deleteDuplication(ListNode pHead) {
            ListNode first = new ListNode(-1);//设置一个空的头结点
            first.next = pHead;
            ListNode p = pHead;
            ListNode last = first;
            while (p != null && p.next != null) {
                if (p.val == p.next.val) {
                    int val = p.val;
                    while (p!= null&&p.val == val)
                        p = p.next;
                    last.next = p;
                } else {
                    last = p;
                    p = p.next;
                }
            }
            return first.next;
        }
    

    复杂度分析:

    • 时间复杂度:O(n)。
    • 空间复杂度:O(n)。
    哎呀,如果我的名片丢了。微信搜索“全菜工程师小辉”,依然可以找到我

    相关文章

      网友评论

        本文标题:剑指offer最优解Java版-删除链表中重复的结点

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