一道笔试题

一个链表，节点里面的内容是字符串，如a->b->c->d->e，要求返回链表如下abcde->bcde->cde->de->e

数据结构：

1 struct NODE
2 {
3     char str[50];
4 
5     NODE *next;
6 };

首先直观的考虑可以用一个两层循环，时间复杂度O(n^2)，当然这个效率是不被接受的

 1 NODE *Linked(NODE *head)
 2 {
 3     assert (head != NULL);
 4 
 5     for (NODE *p1 = head->next; p1 != NULL; p1 = p1->next)
 6     {
 7         for (NODE *p2 = p1->next; p2 != NULL; p2 = p2->next)
 8         {
 9             strcat (p1->str, ",");
10 
11             strcat (p1->str, p2->str);
12         }
13     }
14 
15     return (head);
16 }

这个效率地是因为我们重复的访问了很多节点，如果我们从最后一个节点开始处理的话，每个节点只需要前一个节点的信息，这样可以将事件复杂度降低到O(n)，步骤是先反转链表，再处理链表，最后再将链表反转回来。

 1 NODE *LinkedAnother(NODE *head)
 2 {
 3     assert (head != NULL);
 4 
 5     Reverse (head);
 6 
 7     NODE *p1 = head->next;
 8     NODE *p2 = p1->next;
 9 
10     while ((p1 != NULL) && (p2 != NULL))
11     {
12         strcat (p2->str, ",");
13         strcat (p2->str, p1->str);
14 
15         p1 = p2;
16         p2 = p1->next;
17     }
18 
19     Reverse (head);
20 
21     return (head);
22 }