面试中经常让写的关于链表的代码

还有一个月，各个公司都会开始秋季招聘了，作为即将成为一个被面试的人，说实话，我很紧张也很激动，紧张的原因是我没有进行过技术面试，激动的原因是要看看这大学三年我到底学的怎么样，到底哪些个公司会要我。而与此同时，学校还在进行着每年一度的课程很多的小学期，耽误着大家出去实习，耽误着大家准备找工作的时间，不知道学院的领导们到底是怎么想的。。

今天上午，把以前写过的关于链表的代码重新练习了一下，不全，只是一些常见的，包括：建立链表的相关操作，求链表的长度，对链表实现冒泡排序，完成单链表的逆序和逆序输出，合并两个已经排好序的链表。

下面是代码：

View Code

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 struct Node
  6 {
  7 public:
  8     int data;
  9     Node *next;
 10     Node(){};
 11     Node(int i)
 12     {
 13         data = i;
 14         next = NULL;
 15     }
 16 };
 17 class List
 18 {
 19 public:
 20     Node *head;
 21     Node *curr;
 22     List()
 23     {
 24         head = NULL;
 25         curr = NULL;
 26     }
 27     void insert_from_tail(Node *tmp)
 28     {
 29         if(head == NULL)
 30         {
 31             head = new Node();
 32             head->next = tmp;
 33             curr = tmp;
 34         }
 35         else
 36         {
 37             curr->next = tmp;
 38             curr = tmp;
 39         }
 40     }
 41     int length()const
 42     {
 43         int count = 0;
 44         Node *tmp = head->next;
 45         while(tmp != NULL)
 46         {
 47             tmp = tmp->next;
 48             count++;
 49         }
 50         return count;
 51     }
 52 };
 53 //完成两个节点的值的交换
 54 void Swap(Node *t1,Node *t2)
 55 {
 56     int tmp = t1->data;
 57     t1->data = t2->data;
 58     t2->data = tmp;
 59 }
 60 //冒泡排序
 61 void bubble_sort(List &l)
 62 {        
 63     int len = l.length();
 64     for(int i = len-1 ; i > 0 ; --i)
 65     {
 66         Node *tmp = l.head->next;
 67         for(int j = 0 ; j < i ; ++j)
 68         {
 69             if(tmp->data > tmp->next->data)
 70             {
 71                 Swap(tmp,tmp->next);
 72             }
 73             tmp = tmp->next;
 74         }
 75     }
 76 }
 77 //完成单链表的逆序并输出
 78 void reverse_print(List &l)
 79 {
 80     if(l.head == NULL || l.head->next == NULL)//链表是空
 81     {
 82         return ;
 83     }
 84     Node *p1 = l.head->next;
 85     Node *p2 = l.head->next->next;
 86     p1->next = NULL;//这里一定要让p1->next = NULL，因为逆序后p1实际上是链表的最后一个节点
 87     while(p2 != NULL)
 88     {
 89         Node *tmp = p2->next;
 90         p2->next = p1;    
 91         p1 = p2;
 92         p2 = tmp;
 93     }
 94     l.head->next = p1;//注意这里第一个节点是p1，而不是p2
 95     Node *p = l.head->next;
 96     while(p != NULL)
 97     {
 98         cout<<p->data<<" ";
 99         p = p->next;
100     }
101     cout<<endl;
102 }
103 //合并两个单链表
104 void merge(List l1 ,List l2 ,List &l3)
105 {
106     Node *p1 = l1.head->next;
107     Node *p2 = l2.head->next;
108     while(p1 != NULL || p2 != NULL)
109     {
110         if(p2 == NULL || (p1 != NULL && p1->data <= p2->data))
111         {
112             l3.insert_from_tail(p1);
113             p1= p1->next;
114         }
115         else
116         {
117             l3.insert_from_tail(p2);
118             p2 = p2->next;
119         }
120     }
121 }
122 int main()
123 {
124     /*---------------------------------------*/
125     //初始化单链表
126     int i;
127     Node *p;
128     List l;
129     Node t[5] = {2,1,4,3,0};
130     for(i = 0 ; i < 5 ; ++i)
131     {
132         l.insert_from_tail(&t[i]);    
133     }
134     //单链表的长度
135     cout<<"初始化单链表的长度是：";
136     cout<<l.length()<<endl;
137     cout<<"初始化链表中的数据是：";
138     p = l.head->next;
139     while(p != NULL)
140     {
141         cout<<p->data<<" ";
142         p = p->next;
143     }
144     cout<<endl;
145 
146     /*----------------------------------------*/
147     //排序后的结果
148     bubble_sort(l);
149     cout<<"排序后链表中的数据是：";
150     p = l.head->next;
151     while(p != NULL)
152     {
153         cout<<p->data<<" ";
154         p = p->next;
155     }
156     cout<<endl;
157     /*----------------------------------------*/
158     //逆序单链表
159     cout<<"逆序后链表中的数据是：";
160     reverse_print(l);
161     /*----------------------------------------*/
162     //合并两个拍好序的单链表
163     List l1,l2,l3;
164     Node t1[4] = {1,3,4,5};
165     Node t2[4] = {2,6,7,8};
166     for(i = 0 ; i < 4 ; ++i)
167     {
168         l1.insert_from_tail(&t1[i]);
169         l2.insert_from_tail(&t2[i]);
170     }
171     cout<<"{1，3，4，5}和{2，6，7，8}合并后的链表中的数据：";
172     merge(l1,l2,l3);
173     p = l3.head->next;
174     while(p != NULL)
175     {
176         cout<<p->data<<" ";
177         p = p->next;
178     }
179     cout<<endl;
180     return 0;
181 }

前一段时间问过一个去了人人网C++部门的师哥，说想去大公司的话，代码能力必须过关哦~~~~