leetcode_24題——Swap Nodes in Pairs(リニアテーブルのチェーンストレージ)

Swap Nodes in Pairs  
Total Accepted: 45110 Total Submissions: 138992 My Submissions
Question
 Solution 
 
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.
 
Hide Tags
 
Linked List
Have you met this question in a real interview? 
Yes
 
No
 
Discuss
この問題は何も言うことはありません.主に線形テーブルのチェーンストレージ構造です.注意しなければならないのは、問題の線形テーブルではheadヘッダノードが最初のノードです.

#include<iostream>



using namespace std;



struct ListNode {

	int val;

	ListNode *next;

	ListNode(int x) : val(x), next(NULL) {}

};



ListNode* swapPairs(ListNode* head) {

	ListNode* ptr=head;

	ListNode* ptr0;

	ListNode* ptr1;

	ListNode* ptr2;

	ListNode* temp;



	if(head==NULL)

		return ptr;

	if(ptr->next==NULL)

		return ptr;



	ptr0=ptr;

	ptr1=ptr0->next;



	ptr0->next=ptr1->next;

	ptr1->next=ptr0;

	temp=ptr0;

	ptr0=ptr1;

	ptr1=temp;

	ptr=ptr0;



	ptr2=ptr1->next;

	if(ptr2==NULL)

		return ptr;



	ptr2=ptr2->next;

	if(ptr2==NULL)

		return ptr;

	ptr1=ptr1->next;

	ptr0=ptr0->next;





	while(1)

	{



		ptr1->next=ptr2->next;

		ptr2->next=ptr1;

		ptr0->next=ptr2;

		temp=ptr1;

		ptr1=ptr2;

		ptr2=temp;



		if(ptr2->next==NULL)

			return ptr;

		ptr2=ptr2->next;

		ptr1=ptr1->next;

		ptr0=ptr0->next;



		if(ptr2->next==NULL)

			return ptr;

		ptr2=ptr2->next;

		ptr1=ptr1->next;

		ptr0=ptr0->next;

	}



	return ptr;

}

タイトルのリニア・テーブルに格納されているヘッダ・ノードにデータが格納されていない場合は、また別の方法です.

ListNode* swapPairs(ListNode* head)

{

	ListNode* ptr;

	ListNode* ptr0;

	ListNode* ptr1;

	ListNode* ptr2;

	ListNode* temp;



	ptr=ptr0=head;

	if(ptr==NULL)

		return ptr;

	if(ptr->next==NULL)

		return ptr;

	ptr1=ptr0->next;

	if(ptr1->next==NULL)

		return ptr;

	ptr2=ptr1->next;



	while(1)

	{

		ptr1->next=ptr2->next;

		ptr2->next=ptr1;

		ptr0->next=ptr2;

		temp=ptr1;

		ptr1=ptr2;

		ptr2=temp;



		if(ptr2->next==NULL)

			return ptr;

		ptr2=ptr2->next;

		ptr1=ptr1->next;

		ptr0=ptr0->next;



		if(ptr2->next==NULL)

			return ptr;

		ptr2=ptr2->next;

		ptr1=ptr1->next;

		ptr0=ptr0->next;

	}

	return ptr;

}

int main()

{

	ListNode* head;

	head=(ListNode*)malloc(sizeof(ListNode));

	head->val=1;



	ListNode* ptr2;

	ptr2=(ListNode*)malloc(sizeof(ListNode));

	head->next=ptr2;

	ptr2->next=NULL;

	ptr2->val=2;



	cout<<head->val<<' '<<head->next->val<<endl;



	ListNode* head1;

	head1=swapPairs(head);

	cout<<head1->val<<' '<<head1->next->val<<endl;







}