# O(N) solution using ListNode and HashMap

• 1\ store all the characters in a list of listnode. The index+1 is their frequency.
2\ each time you encounter a character, if it already exists, remove it from old index and add it to new index. else, add it to list[0].

``````public class Solution {
private class ListNode{
public char val;
public int count;
public ListNode pre;
public ListNode next;
public ListNode(char c) {
this.val = c;
count = 0;
pre = null;
next = null;
}
}
public string FrequencySort(string s) {
var memo = new List<ListNode>();
var dic = new Dictionary<char, ListNode>();

foreach(var c in s){
var n = ++dic[c].count;
if(n == 1){
}
else{
RemoveNode(memo, dic[c], n-2);
}
}
var N = memo.Count();
var sb = new StringBuilder();
for(var i = N-1; i >= 0; i--){
var node = memo[i];
while(node != null){
var j = i+1;
while(j > 0){
sb.Append(node.val);
j--;
}
node = node.next;
}
}
return sb.ToString();
}

private void AddNode(IList<ListNode> memo, ListNode x, int idx){
var N = memo.Count();
if(idx == N){
}
else{
x.next = memo[idx];
if(memo[idx] != null){
memo[idx].pre = x;
}
memo[idx] = x;
}
}

private void RemoveNode(IList<ListNode> memo, ListNode x, int idx){
if(memo[idx] == x){
memo[idx] = x.next;
if(x.next != null){
x.next.pre = null;
}
x.next = null;
x.pre = null;
}
else{
x.pre.next = x.next;
if(x.next != null){
x.next.pre = x.pre;
}
x.next = null;
x.pre = null;
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.