带头结点的单链表笔试中的考点（经过gcc调试）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. 
   
5. typedef struct node
   
6. {
   
7.     int data;
   
8.     struct node *next;
   
9. }link;
   
10. 
    
11. link *creat(void);
    
12. link *insert(link *head, int postion, int val);
    
13. link *del_node(link *head, int val);
    
14. link *search(link *head, int val);
    
15. void printl(link * head);
    
16. int length(link *phead);
    
17. link *reverse(link *head);
    
18. 
    
19. int main(void)
    
20. {
    
21.     link *head, *p;
    
22.     int d, pos;
    
23.     
    
24.     head = creat();
    
25.     printl(head);
26. 
    
27.     printf("please input insert data:");
    
28.     scanf("%d", &d);
    
29.     printf("please input insert postion:");
    
30.     scanf("%d", &pos);
    
31.     insert(head, pos, d);
    
32.     printl(head);
    
33.     
34.     printf("please input search data:");
    
35.     scanf("%d", &d);
    
36.     p = search(head, d);
    
37.     if(!p)
38.     {
39.         printf("can't search the data %d\n", d);
40.     }
41.     else
42.     {
43.         printf("the data we search:%d\n", p->data);
    
44.     }
45.     printl(head);
    
46.     
47.     printf("please input del data:");
    
48.     scanf("%d", &d);
    
49.     del_node(head, d);
    
50.     printl(head);
51. 
    
52.     printf("the length of the list is: %d\n", length(head));  
53.   
    
54.     printf("reverse the list:");
    
55.     p = reverse(head);
    
56.     printl(p);
    
57.     
    
58.     return 0;
    
59. }
    
60. 
    
61. /*创建链表，从输入终端输入数据需要考虑终止条件*/
    
62. link *creat(void)
    
63. {
    
64.     link *head == NULL;
65.     link *tail == NULL;
66.     link *cur == NULL;
    
67.     int x;    
    
68. 
    
69.     head = (link *)malloc(sizeof(link));
    
70.     if(!head)
    
71.     {
    
72.         printf("malloc error\n");
    
73.         exit(1);
    
74.     }
    
75.     tail = head;
    
76.     
    
77.     while(1)
    
78.     {
    
79.         printf("please input data:");
    
80.         scanf("%d", &x);
    
81.         if(x <= 0)
    
82.         {
    
83.             break;
    
84.         }
    
85.         cur = (link *)malloc(sizeof(link));
    
86.         if(!cur)
    
87.         {
    
88.             printf("malloc error\n");
    
89.             exit(1);
    
90.         }
    
91.         cur->data = x;
    
92.         cur->next = NULL;
    
93.         tail->next = cur;
    
94.         tail = cur;
    
95.     }
    
96.     
    
97. 
    
98.     printf("creat list success\n");
    
99.     
    
100.     return head;
     
101. }
     
103. /*插入函数，通过while循环获取要插入的位置的前一个位置的指针，若获取要插入位置的指针，插入将无法插入第i个位置*/
     
104. link *insert(link *head, int postion, int val)
     
105. {
     
106.     link *p = head;
     
107.     link *q = NULL;
     
108.     int i = 0;
     
109.     while(p && (i < postion-1))
     
110.     {
     
111.         p = p->next;
     
112.         i++;
     
113.     }
     
114.     
     
115.     /*此处p为空表明链表长度不够，i>postion-1检查传入参数是否合法（如postion<1）*/
     
116.     if((!p) || (i > postion-1))
     
117.     {
     
118.         printf("insert error\n");
     
119.         exit(2);
     
120.     }
     
121.     q = (link *)malloc(sizeof(link));
     
122.     if(!q)
     
123.     {
     
124.         printf("malloc error\n");
     
125.         exit(1);
     
126.     }
     
127.     q->data = val;
     
128.     q->next = p->next;
     
129.     p->next = q;
     
130. 
     
131.     printf("insert success\n");
     
132.     
     
133.     return head;
     
134. }
     
136. /*查找函数，充分考虑两种情况，一种为所找元素不存在，一种为所找元素存在，分别返回不同的值*/
     
137. link *search(link *head, int val)
     
138. {
     
139.     link *p = NULL;
     
140.     if(!head)
     
141.     {
     
142.         printf("error\n");
     
143.         return NULL;
     
144.     }
     
145.     p = head->next;
     
146.     while(p && (p->data != val))
     
147.     {
     
148.         p = p->next;
     
149.     }
     
150.     if(!p)
     
151.     {
     
152.         printf("can't search the data\n");
     
153.         return NULL;
     
154.     }
     
155.     else
     
156.     {
     
157.         return p;
     
158.     }
     
159. }
     
161. /*删除结点，关键点在建立一个临时指针保存需要删除结点的前驱*/
     
162. link *del_node(link *head, int val)
     
163. {
     
164.     link *p = NULL;
     
165.     link *q = NULL;
     
166.     if(!head)
     
167.     {
     
168.         printf("empty list\n");
     
169.         return NULL;
     
170.     }
     
171.     p = head->next;
     
172.     q = head;
     
173.     for( ; p; p=p->next)
     
174.     {    
     
175.         if(val == p->data)
     
176.         {
     
177.             q->next = p->next;
     
178.             free(p);
179.             /*如果不理解前面两句，可以看一下下面我注释的代码*/
     
180.             #if 0
     
181.             if(q == head)
     
182.             {
     
183.                 head->next = p->next;
     
184.                 free(p);
     
185.             }
     
186.             else
     
187.             {
     
188.                 q->next = p->next;
     
189.                 free(p);
     
190.             }
     
191.             #endif
     
192.             
     
193.             printf("del node success\n");
     
194.             return head;
     
195.         }
     
196.         q = p;
     
197.     }
     
198.     printf("%d could not been found\n", val);
     
199.     return NULL;
     
200. }
     
202. /*从第一个结点开始打印，在打印之前需要去掉头结点，避免打出无效的数据*/
     
203. void printl(link * head)
     
204. {
     
205.     link *p = NULL;
     
206.     if(!head)
     
207.     {
     
208.         return;
     
209.     }
     
210.     for(p=head->next; p; p=p->next)
     
211.     {
     
212.         printf("%d ", p->data);
     
213.     }
     
214.     printf("\n");
     
215.     return;
     
216. }
     
218. /*因为头结点为链表中附加的结点，所以计算长度的时候没有将其计算在内*/
     
219. int length(link *phead)
     
220. {
     
221.     link *p = phead->next;
     
222.     int count = 0;
     
223.     while(p)
     
224.     {
     
225.         p = p->next;
     
226.         count++;
     
227.     }
     
228.     return count;
     
229. }
     
230. 
     
231. /*反转函数相对较难，其解析部分在文章后面有说明*/
     
232. link *reverse(link *head)
     
233. {
     
234.     link *pre = NULL;
     
235.     link *cur = NULL;
     
236.     link *nex = NULL;
     
237.     
     
238.     if(!head || !head->next)
     
239.     {
     
240.         return head;
     
241.     }    
     
242.     pre = head->next;
     
243.     cur = pre->next;    
     
244. 
     
245.     while(cur)
     
246.     {
     
247.         nex = cur->next;
     
248.         cur->next = pre;
     
249.         pre = cur;
     
250.         cur = nex;
     
251.     }
     
252.     
     
253.     head->next->next = NULL;
     
254.     head->next = pre;
     
255.     return head;
     
256. }

上面实现了非递归算法反转链表，下面给出其递归算法

typedef struct node

{  

    int data;  

    struct node * next;  

} link ;  

  

//reverse a link list recursively  

link * reverse(link * pre, link * cur)  

{  

    if(!cur)  

        return pre;    

    link *head = reverse(cur, cur->next);  

    cur->next = pre;  

    return head;  

}  

如果对reverse反转函数的完全解析感兴趣可以参考我下面的文章：

http://blog.chinaunix.net/space.php?uid=24919665&do=blog&id=362785

下面再贴出一些其他的有趣考点：

四道有趣的单链表面试题（找出链表的中间元素、链表排序、判断一个单链表是否有环、是否相交）

以下给出链表结点的数据结构：

1  typedef struct _list_node
2 {
3     double keyVal;
4     struct _list_node *next;
5 }ListNode;

 

Q1找出链表的中间元素

Code
 1 ListNode* find_midlist(ListNode* head)
 2 {
 3     ListNode *p1, *p2;
 4     
 5     if (head == NULL || head->next == NULL)
 6     {
 7         return head;
 8     }
 9     p1 = p2 = head;
10     while (1)
11     {
12         if (p2->next != NULL && p2->next->next != NULL)
13         {
14             p2 = p2->next->next;
15             p1 = p1->next;
16         }
17         else
18         {
19             break;
20         }
21     }
22     return p1;
23 }

思路分析：

 单链表的一个比较大的特点用一句广告语来说就是“不走回头路”，不能实现随机存取（random access）。如果我们想要找一个数组a的中间元素，直接a[len/2]就可以了，但是链表不行，因为只有a[len/2 - 1] 知道a[len/2]在哪儿，其他人不知道。因此，如果按照数组的做法依样画葫芦，要找到链表的中点，我们需要做两步（1）知道链表有多长（2）从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n（n为链表的长度）的时间复杂度了。有没有更好的办法呢？有的。想法很简单：两个人赛跑，如果A的速度是B的两倍的话，当A到终点的时候，B应该刚到中点。这只需要遍历一遍链表就行了，还不用计算链表的长度。

 上面的代码就体现了这个想法。

Q2链表排序

Code
 1 double cmp(ListNode *p ,ListNode *q)
 2 {return (p->keyVal - q->keyVal);}
 3 
 4 ListNode* mergeSortList(ListNode *head)
 5 {
 6     ListNode *p, *q, *tail, *e;
 7     int nstep = 1;
 8     int nmerges = 0;
 9     int i;
10     int psize, qsize;
11     if (head == NULL || head->next == NULL)
12     {return head;}
13     while (1)
14     {   p = head;
15         tail = NULL;
16         nmerges = 0;
17         while (p)
18         {   nmerges++;  q = p;  psize = 0;
19             for (i = 0; i < nstep; i++){
20                 psize++;
21                 q = q->next;
22                 if (q == NULL)break;
23 }
24             qsize = nstep;
25             while (psize >0 || (qsize >0 && q))
26 {
27                 if (psize == 0 ){e = q; q = q->next; qsize--;}
28                 elseif (q == NULL || qsize == 0){e = p; p = p->next; psize--;}
29                 elseif (cmp(p,q) <= 0){e = p; p = p->next; psize--;}
30                 else{e = q; q = q->next; qsize--;}
31                 if (tail != NULL){tail->next = e;}
32                 else{head = e;}
33                 tail = e;
34               }
35             p = q;
36         }
37         tail->next = NULL;
38         if (nmerges <= 1){return head;}
39         else{nstep <<= 1;}
40     }
41 }

思路分析：

  链表排序最好使用归并排序算法。堆排序、快速排序这些在数组排序时性能非常好的算法，在链表只能“顺序访问”的魔咒下无法施展能力；但是归并排序却如鱼得水，非但保持了它O(nlogn)的时间复杂度，而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。真是好得不得了啊，哈哈。以上程序是递推法的程序，另外值得一说的是看看那个时间复杂度，是不是有点眼熟？对！这就是分治法的时间复杂度，归并排序又是divide and conquer。

Q3 判断一个单链表是否有环

Code
 1 int is_looplist (ListNode *head)
 2 {
 3     ListNode *p1, *p2;
 4     p1 = p2 = head;
 5 
 6     if (head == NULL || head->next == NULL)
 7     {
 8         return 0;
 9     }
10 
11     while (p2->next != NULL && p2->next->next != NULL)
12     {
13         p1 = p1->next;
14         p2 = p2->next->next;
15         if (p1 == p2)
16         {
17             return 1;
18         }
19     }
20 
21     return 0;
22 
23 }

思路分析：

  这道题是《C专家编程》中的题了。其实算法也有很多，比如说：我觉得进行对访问过的结点进行标记这个想法也不错，而且在树遍历等场合我们也经常使用。但是在不允许做标记的场合就无法使用了。在种种限制的条件下，就有了上面的这种算法，其实思想很简单：就像两个人在操场上跑步一样，只要有个人的速度比另一个人的速度快一点，他们肯定会有相遇的时候的。不过带环链表与操场又不一样，带环链表的状态是离散的，所以选择走得快的要比走得慢的快多少很重要。比如说这里，如果一个指针一次走三步，一个指针一次走一步的话，很有可能它们虽然在一个环中但是永远遇不到，这要取决于环的大小以及两个指针初始位置相差多少了。呵呵。你能看出两个指针的速度应该满足什么关系才能在有环的情况下相遇吗？如果你知道，不妨跟我讨论一下，呵呵。

Q4如何判断两个链表是否相交，并找出交点

思路：先遍历第一个链表，记住最后一个节点，再遍历第二个链表，得到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交。若相交，再分别从头同步遍历，直到相同的结点。

Node* checkLink(Node* pHead1,Node* pHead2)
{
     Node* p1=pHead1,*p2=pHead2;
     int i=1,j=1;
     if(p1==NULL || p2==NULL)
        return NULL;
     if(p1==p2)
        return p1;
     while(p1->pNext!=NULL)
     {
        p1=p1->pNext;
        i++;
     }
     while(p2->pNext!=NULL)
     {
        p2=p2->pNext;
        j++;
     }
     if(p1!=p2)
        return NULL;
     else
     {

p1=pHead1,p2=pHead2;
        for(int k=0;k        {
              if(i>j)
                     p1=p1->pNext;
              else
                     p2=p2->pNext;
        }
        while(p1!=p2)
        {
              p1=p1->pNext;
              p2=p2->pNext;
        }
        return p1;
     }
}