1 #include "000库函数.h"
2
3
4
5
6 struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(NULL) {}
10 };
11 //注意，该链表是无头结点,为了不乱，自己加了一个头结点
12 class Solution {
13 public:
14 ListNode* swapPairs(ListNode* head) {
15 if (!head || head->next == NULL)return head;
16 ListNode* p = new ListNode(0);
17 p->next = head;
18 head = p;
19 while (1) {
20 ListNode *i, *j;
21 i = p->next;
22 j = i->next;
23 i->next = j->next;
24 j->next = i;
25 p->next = j;
26 if (!(p->next))
27 return head->next;
28 p = p->next->next;
29 if (!(p->next) || !(p->next->next))
30 return head->next;
31 }
32 return head->next;
33 }
34
35
36 };
37
38 //使用递归，比自己更耗时，但节约内存
39 //实际上利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换：
40 class Solution {
41 public:
42 ListNode* swapPairs(ListNode* head) {
43 if (!head || !head->next) return head;
44 ListNode* p = head;
45 head = head->next;
46 p->next = head->next;
47 head->next = p;
48 p->next = swapPairs(p->next);
49 return head;
50 }
51 };
52
53
54 void T024() {
55 ListNode* L = new ListNode(0);
56 ListNode*p = L;
57 for (int i = 0; i < 6; ++i) {
58 ListNode*q = new ListNode(0);
59 q->val = i + 1;
60 p->next = q;
61 p = q;
62 }
63 p->next = NULL;
64 p = L->next;
65 while (p) {
66 cout << p->val << ' ';
67 p = p->next;
68 }
69 cout << endl;
70
71 Solution S;
72 p = S.swapPairs(L->next);
73 while (p) {
74 cout << p->val << ' ';
75 p = p->next;
76 }
77 cout << endl;
78
79 }
