链表——两两交换链表中的节点

#include<iostream>
using namespace std;

struct ListNode 
{
	int val;
	ListNode* next;
	ListNode(int val) :val(val), next(NULL) {};
};

// 根据数组创建链表
ListNode* Arr2Chain(int a[], int num)
{
	ListNode* head = NULL;
	ListNode* add = NULL;
	ListNode* tail = NULL;

	for (int i = 0; i < num; i++)
	{
		ListNode* add = new ListNode(a[i]);
		if (tail != NULL)
		{
			tail->next = add;
			tail = add;
		}
		else 
		{
			head = tail = add;
		}
	}
	return head;
}

class Solution 
{
public:
	ListNode* swapPairs(ListNode* head)
	{
		ListNode* dummyHead = new ListNode(0);		// 设置虚拟头节点，并初始化值为0
		dummyHead->next = head;
		ListNode* cur = dummyHead;

		while (cur->next != NULL && cur->next->next != NULL)
		{
			ListNode* temp = cur->next;					// 记录临时节点
			ListNode* temp1 = cur->next->next->next;	// 记录临时节点

			cur->next = cur->next->next;
			cur->next->next = temp;
			cur->next->next->next = temp1;

			cur = cur->next->next;						// cur移动两位，准备下一轮交换
		}
		return dummyHead->next;
	}

	void printList(ListNode* cur)
	{
		while (cur != NULL)
		{
			cout << cur->val << " ";
			cur = cur->next;
		}
		cout << endl;
	}
};

int main() {
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	int num = sizeof(a) / sizeof(a[0]);
	cout << "num = " << num << endl;
	Solution s2;

	ListNode* head2 = Arr2Chain(a, num);
	s2.printList(head2);

	ListNode* cur = s2.swapPairs(head2);
	s2.printList(cur);
}