比如對于鏈表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 閱讀(1389)
評論(0) 編輯 收藏 引用 所屬分類:
筆試+面試總結