题解 | #删除链表中重复的结点#

删除链表中重复的结点

http://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef

算法思想一：递归

解题思路：

主要利用递归算法对有序链表递归遍历删除重复的节点

1、特殊情况，如果 pHead 为空，那么肯定没有值出现重复的节点，直接返回 pHead ；如果 pHead.next 为空，那么说明链表中只有一个节点，也没有值出现重复的节点，也直接返回 pHead。

2、如果 pHead.val != pHead.next.val ，说明头节点的值不等于下一个节点的值，所以当前的 pHead节点必须保留；但是 pHead.next 节点要不要保留呢？需要对 pHead.next 进行递归，即对 pHead.next 作为头节点的链表，去除值重复的节点。所以 pHead.next = self.deleteDuplication(pHead.next).
3、如果 pHead.val == pHead.next.val ，说明头节点的值等于下一个节点的值，所以当前的 pHead节点必须删除，并且 pHead之后所有与 pHead.val 相等的节点也都需要删除；删除到哪个节点为止呢？需要用 move 指针一直向后遍历寻找到与 pHead.val 不等的节点。此时 move 之前的节点都不保留了，因此返回 self.deleteDuplication(move);

4、返回结果，如果 pHead.val != pHead.next.val ，头结点需要保留，因此返回的是 pHead；如果 pHead.val == pHead.next.val ，头结点需要删除，需要返回的是self.deleteDuplication(move);

图解：

代码展示

Python版本

class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        if pHead.val != pHead.next.val:
            pHead.next = self.deleteDuplication(pHead.next)
        else:
            move = pHead.next
            while move and pHead.val == move.val:
                move = move.next
            return self.deleteDuplication(move)
        return pHead

复杂度分析：

时间复杂度O(N)：N是链表节点数量，递归遍历一次

空间复杂度O(N)：递归调用的时候会用到了系统的栈。

算法思想二：一次遍历

解题思路：

1、由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy）指向链表的头节点。
2、让指针 cur 指向链表的哑节点，随后开始对链表进行遍历。如果当前cur.next 与cur.next.next 对应的元素相同，那么我们就需要将 cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 x，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 x 为止。此时，我们将链表中所有元素值为 x 的节点全部删除。
3、如果当前 cur.next 与 cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为 cur.next 的节点，那么我们就可以将 cur 指向 cur.next。
当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 dummy.next 即可。
需要注意， cur.next 以及 cur.next.next 可能为空节点，如果不加以判断，可能会产生运行错误

图解：

代码展示

JAVA版本

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if (pHead == null) {
            return pHead;
        }
        // 创建哑节点
        ListNode dummy = new ListNode(-1);
        dummy.next = pHead;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}