比如对于链表a->b->c->d->g;
交换之后应该是b->a->d->c->g;
对于这种题目应该问清楚面试官可否仅进行节点值的交换？如果面试官说可以那就非常简单了，否则就得进行链表指针的变换，不过一般面试官考察此题的目的都是为了考察指针操作，所以最好问清楚～
下面是程序：
1 #include <cstdio>
2 #include <string.h>
3
4 typedef struct list {
5 int data;
6 struct list *next;
7 } list;
8
9 list *list_swap(list *head) {
10 list *p = head;
11 if (!p) return head;
12 list *q = p->next;
13 if (!q) return head;
14 list *pre = NULL;
15 while (p && q) {
16 if (head == p) head = q;
17 if (pre != NULL) {
18 pre->next = q;
19 }
20 pre = p;
21 p->next = q->next;
22 q->next = p;
23 p = p->next;
24 if (!p) return head;
25 q = p->next;
26 }
27
28 return head;
29 }
30
31 list *list_value_swap(list *head) {
32 list *p = head;
33 if (!p) return head;
34 list *q = p->next;
35 if (!q) return head;
36 while (p && q) {
37 list temp;
38 temp.data = p->data;
39 p->data = q->data;
40 q->data = temp.data;
41 p = q->next;
42 if (!p) return head;
43 q = p->next;
44 }
45
46 return head;
47 }
48
49 int main() {
50 list *head = new list;
51 head->data = 1;
52 head->next = new list;
53 head->next->data = 2;
54 head->next->next = new list;
55 head->next->next->data = 3;
56 head->next->next->next = new list;
57 head->next->next->next->data = 4;
58 head->next->next->next->next = new list;
59 head->next->next->next->next->data = 5;
60 head->next->next->next->next->next = NULL;
61 head = list_swap(head);
62 while (head) {
63 printf("%d ", head->data);
64 head = head->next;
65 }
66 printf("\n");
67 return 0;
68 }
69
posted on 2012-04-21 10:57
myjfm 阅读(1362)
评论(0) 编辑 收藏 引用 所属分类:
笔试+面试总结