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

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我