024两两交换链表中的节点

 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 }