题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
例：给定 1->2->3->4, 你应该返回 2->1->4->3.
解决方案
主要还是弄清楚指针指来指去的顺序。还有注意把两两交换后的节点对连起来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* swapPair(ListNode* n1)
{
ListNode* p = n1;
ListNode* q = n1->next->next;
n1 = n1->next;
n1->next = p;
n1->next->next = q;
return n1;
}
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next)
return head;
ListNode* h = head;
ListNode* link = head;
bool flag = true;
do
{
ListNode* tmp = h;
tmp=swapPair(tmp);
if (flag)
{
head = tmp;
flag = false;
}
else
{
link->next = tmp;
link = tmp->next;
}
h = tmp->next->next;
if (!h||!h->next)
break;
} while (true);
return head;
}
|