Base idea:

1.sort the list use extra men O(1) method like heap sort(I didn't implement the algorithm)

2.use size 2 window compare elements.

```
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums.sort()
for index in xrange(0, len(nums), 2):
if len(nums) == index + 1:
return nums[index]
if not nums[index] == nums[index + 1]:
return nums[index]
```