Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear onlyonce.

For example, Given1->1->2, return1->2. Given1->1->2->3->3, return1->2->3.

1.HashTable

O(N)

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        hashtable={}
        current = head
        pre = None
        while current is not None:
            if current.val in hashtable:
                pre.next = current.next
            else:
                hashtable[current.val] = True
                pre = current
            current = current.next
        return head

2.移除有序链表中的重复项需要定义个指针指向该链表的第一个元素，然后第一个元素和第二个元素比较，如果重复了，则删掉第二个元素，如果不重复，指针指向第二个元素。这样遍历完整个链表，则剩下的元素没有重复项

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        current = head
        while current and current.next:
            if current.val ==current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        return head