题目

给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
http://www.lintcode.com/zh-cn/problem/single-number/

分析

由于除目标数之外的其他数字，都会出现两次，很容易联想到抵消。假设有一个容器，向其中添加数时，若该数不存在，就存储下来，若存在，就删除掉这个数。当所有的数字都添加到容器中后，容器中唯一剩下的数就是要早的落单数。

那么，应该用什么充当容器呢？容器会频繁进行增加和删除的操作，数组并不合适，带头节点的单链表是一个不错的选择。插入数字时，若链表中不包含这个数字，就创建一个新节点添加到链表末尾；若存在，就删除对应的节点。数组遍历结束后，头节点后面的节点，存储的就是落单的数。

代码

主要就是实现一个（带头节点的）单链表的查找和删除。删除时注意一下删除末尾元素的特殊情况即可。

class ListNode{
    ListNode next;
    int val;
    
    ListNode(){
        this.next = null;
    }
    
    ListNode(int val){
        this.val = val;
        this.next = null;
    }
}

class List{
    ListNode head = null;
    ListNode last = null;
    
    List(){
        head = last = new ListNode();
    }
    
    void add(int val){
        last.next = new ListNode(val);
        last = last.next;
    }
    // 查找目标值的前驱节点，由于有头节点的存在，直接从头节点后面的第一个元素开始
    ListNode findPrevious(int val){
        for(ListNode pre = head; pre.next != null; pre = pre.next){
            if(pre.next.val == val) return pre;
        }
        return null;
    }
    //删除节点，若被删除的节点为last时，需要更新last
    void remove(ListNode node){
        ListNode target = node.next;
        node.next = target.next;
        
        if(target == this.last){
            this.last = node;
        }
    }
    
    void addOrRemove(int val){
        ListNode pre = this.findPrevious(val);
        if(pre == null){
            this.add(val);
        }else{
            this.remove(pre);
        }
    }
    
}

public class Solution {
    /*
     * @param A: An integer array
     * @return: An integer
     */
    public int singleNumber(int[] A) {
        // write your code here
        List list = new List();
        for(int i=0; i < A.length; i++){
            list.addOrRemove(A[i]);
        }
        
        return list.last.val;
    }
}