转载

大公司面试经典数据结构与算法题C#解答

几个大公司（IBM、MicroSoft and so on）面试经典数据结构与算法题C#解答

1.链表反转

我想到了两种比较简单的方法

第一种是需要开一个新的链表，将原链表的元素从后到前的插入到新链表中（也就是原链表第一个元素被插入成新链表的最后一个元素）。

第二种是不需要开新的链表，而是逐步反转原链表中元素的指向，例如：

原链表是 1->2->3->4->null 被逐步修改为 ①2->1->null、3->4->null ②3->2->1->null、4->null ③4->3->2->1->null

最后再将head指向4。

  1 namespace 链表反转   2 {   3     class Node    4     {   5         public int Num { get; set; }   6         public Node Next { get; set; }   7     }   8     class Program   9     {  10         static void Main(string[] args)  11         {  12             NodeList list = new NodeList();  13             list.Add(1);  14             list.Add(2);  15             list.Add(3);  16             list.Add(4);  17             list.Add(5);  18             list.Reverse1();  19             list.Print();  20   21             NodeList list1 = list.Reverse();  22             list1.Print();  23   24             Console.ReadKey();  25         }  26     }  27   28     class NodeList  29     {  30         public Node Head { get; set; }  31         public void Add(int num)  32         {  33             if (Head == null)  34             {  35                 Head = new Node();  36                 Head.Next = new Node() { Num = num };  37             }  38             else  39             {  40                 Node tn = Head;  41                 while (tn.Next != null)  42                 {  43                     tn = tn.Next;  44                 }  45                 tn.Next = new Node() { Num = num };  46             }  47         }  48   49         public void Print()  50         {  51             Node tn = Head;  52             while(tn.Next!=null)  53             {  54                 tn = tn.Next;  55                 Console.WriteLine(tn.Num);  56             }      57         }  58   59         //需要开新链表的反转  60         public NodeList Reverse()  61         {  62             NodeList list = new NodeList();  63             Node tn = Head;  64             Node newTn = null;  65             while (tn.Next != null)  66             {  67                 tn = tn.Next;  68                 if (newTn == null)  69                 {  70                     newTn = new Node() { Num = tn.Num };  71                 }  72                 else  73                 {  74                     newTn = new Node() { Num = tn.Num,Next=newTn };  75                 }  76             }  77             list.Head = new Node();  78             list.Head.Next = newTn;  79             return list;  80         }  81   82         //不需要开新链表的反转  83         public void Reverse1()  84         {  85             Node n1 = Head.Next;  86             Node n2 = Head.Next.Next;  87             //第一个节点也就是反转后的最后一个节点，Next要指向null  88             Node first = Head.Next;  89             first.Next = null;  90             //如果链表为空或者链表只有一个元素那就无需调整  91             if (n2 == null || n1 ==null)  92             {  93                 return;  94             }       95             //先用Head指向n2的下一个元素，再将n2的Next指向n1，最后将n1和n2向右移动  96             while (n2.Next != null)  97             {  98                 Head.Next = n2.Next;  99                 n2.Next = n1; 100                 n1 = n2; 101                 n2 = Head.Next; 102             } 103             //最后要将头结点指向链表反转前的最后一个元素 104             Head.Next = n2; 105             //因为判断条件只调整到最后一个元素的前一个元素，所以要调整最后一个元素的Next指向 106             n2.Next = n1;            107         } 108     }

2.字符串查找第一个不重复的字母

基本原理：第一遍遍历字符串时，用hash表存储每个字符出现的次数，第二遍遍历字符串时，筛选出第一个hash中对应保存的出现次数为1的字符。

 1 namespace 字符串查找第一个不重复的字母  2 {  3     class Program  4     {  5         static Hashtable hash = new Hashtable();     6         static void Main(string[] args)  7         {  8             string s = "asfgasjfoiwoeqkwzxc";  9             Count(s); 10             Console.WriteLine(Search(s)); 11             Console.ReadKey(); 12         } 13  14         static void Count(string s) 15         { 16             for (int i = 0; i < s.Length; i++) 17             { 18                 if (hash.Contains(s[i])) 19                 { 20                     hash[s[i]] = (int)hash[s[i]]+1; 21                 } 22                 else 23                 { 24                     hash[s[i]] = 1; 25                 } 26             } 27         } 28  29         static char Search(string s) 30         { 31             for (int i = 0; i < s.Length; i++) 32             { 33                 if ((int)hash[s[i]] == 1) 34                 { 35                     return s[i]; 36                 } 37             } 38             return '#'; 39         } 40     } 41 }