【題目】
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
連結清單中,每兩個交換一下位置。
https://leetcode.com/problems/swap-nodes-in-pairs/
【解析】
看了某人的解析,圖畫的出神入化,不禁也想模仿。
http://blog.csdn.net/summerdj/article/details/51457424
建立連結清單如下:
head為目前頭指針
pre為前一個指針
q為目前操作臨時指針
p為交換後的連結清單的頭指針的前一個指針
ListNode* p=new ListNode(0);
p->next=head->next;
ListNode* pre=p;
ListNode* q=head->next;
進入第一次循環:
head->next=q->next;
q->next=head;
head=head->next;
pre->next=q;
pre=q->next;
進入第二次循環:
q=head->next;
head->next=q->next;
q->next=head;
head=head->next;
pre->next=q;
pre=q->next;
以此類推,當發現next對應的位址為NULL時,則連結清單周遊結束
p->next 即為整個連結清單的開頭,return,結束。
【程式】
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* p=new ListNode(0);
p->next=head->next;
ListNode* pre=p;
ListNode* q=head->next;
while(head->next){
q=head->next;
if(q->next){
head->next=q->next;
q->next=head;
head=head->next;
pre->next=q;
pre=q->next;
}
else{
head->next=NULL;
q->next=head;
pre->next=q;
}
}
return p->next;
}
};