C++实现算法题之奇偶链表

题目：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

示例 1:
输入: 1->2->3->4->5->NULL
输出 : 1->3->5->2->4->NULL
示例 2 :
输入 : 2->1->3->5->6->4->7->NULL
输出 : 2->3->6->7->1->5->4->NULL

#include <iostream>

using namespace std;

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

// 分离节点后合并
ListNode* oddEvenList(ListNode* head)
{
	// 如果链表为空，则直接返回链表。
	if (head == nullptr)
	{
		return head;
	}

	ListNode* evenHead = head->next;
	// odd = head是奇数节点
	ListNode* odd = head;
	// even = head->next是偶数节点
	ListNode* even = evenHead;

	// 通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。
	while (even != nullptr && even->next != nullptr)
	{
		// 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点
		// 此时 odd 变成 even 的后一个节点。
		odd->next = even->next;
		odd = odd->next;

		// 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点
		// 此时 even 变成 odd 的后一个节点。
		even->next = odd->next;
		even = even->next;
	}
	// 将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并
	odd->next = evenHead;

	return head;
}

int main()
{
	// 创建链表
	ListNode* head = new ListNode(1);
	ListNode* node1 = new ListNode(2);
	ListNode* node2 = new ListNode(3);
	ListNode* node3 = new ListNode(4);
	ListNode* node4 = new ListNode(5);

	head->next = node1;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = nullptr;

	// 奇偶链表
	head = oddEvenList(head);

	// 打印链表
	while (head != nullptr)
	{
		cout << head->val << endl;
		head = head->next;
	}

	return 0;
}