首页 > 代码库 > Leetcode ---- Swap Nodes in Pairs

Leetcode ---- Swap Nodes in Pairs

题目链接

题意:给出单链表头指针,要求交换链表中每一对相邻的结点.

注意:不可以改变链表中结点的值,只可以使用常量空间.

 

附上代码:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *swapPairs(ListNode *head) {
12         if (head == NULL || head->next == NULL) {
13             return head;
14         }
15         ListNode *p = head, *q = head->next, *pre = head;
16         while (q != NULL) {
17             p->next = q->next;
18             q->next = p;
19             if (pre == head) {
20                 head = q;
21             } else {
22                 pre->next = q;
23             }
24             swap(q, p);
25             pre = q;
26             p = q->next;
27             if (p == NULL) {
28                 break;
29             } 
30             q = q->next->next;
31         }
32         
33         return head;
34     }
35 };