First non duplicate character in string C++

Find out the first non duplicate character in a string.
eg: "nasa" output: 'n' 
Require to scan the string only once.

思路：要求只能扫一遍string，既然时间严格限制，那只好多用空间了。一个map用来计数，一个double linkedlist用来存character candidates.最后总时间是O(n).
注：本代码未测试，懒得自己写double linked node的定义了。。

0. //assume that s is nonempty  
1. char firstnondup(string s){  
2.   
3.    unordered_map<char, ListNode*>  visited;  
4.   
5.    ListNode *tail = new ListNode(s[0]);  
6.   
7.    ListNode dummy(0);  
8.   
9.    dummy.next = tail;  
10.   
11.    tail->prev = dummy;  
12.   
13.    visited[s[0]] = tail;  
14.   
15.    for(int i = 1; i < s.length(); i++){  
16.    
17.       //if first occured  
18.       if(visited.find(s[i]) == visited.end()){  
19.   
20.         ListNode *cur = new ListNode(s[i]);  
21.   
22.         visited[s[i]] = cur;  
23.   
24.         tail->next = cur;  
25.   
26.         cur->prev = tail;  
27.   
28.         tail = cur;  
29.   
30.       }  
31.   
32.      else{  
33.   
34.        //if second occured, delete node  
35.        if(visited[s[i]] != NULL) {  
36.   
37.             ListNode *tmp = visited[s[i]]->prev;  
38.   
39.             tmp->next = visited[s[i]]->next;  
40.   
41.             visited[s[i]]->next->prev = tmp;  
42.   
43.             if(visited[s[i]] == tail) tail = tmp;  
44.   
45.             delete visited[s[i]];  
46.       }  
47.   
48.       //if more than secondly occured, just continue  
49.     }  
50.   }  
51.   
52. return dummy.next.val;  
53.   
54. }  
55.   
56.