【C++】链表反转

//test 反转链表

#include <iostream>
using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
};

//打印链表
void printList(ListNode* head)
{
	while (head)
	{
		cout << head->val;
		head = head->next;
		if (head)
			cout << "->";
	}
	cout << "\n";
}

//反转链表
//1.非递归法
ListNode* reverseList1(ListNode* head)
{
	//初始化ListNode
	ListNode *pre = NULL;
	ListNode *cur = head;
	ListNode *nex = NULL;

	while (cur)
	{
		//当前链表非空，进行以下处理
		nex = cur->next;	//当前值的下一位
		cur->next = pre;
		pre = cur;	//当前值赋给pre
		cur = nex;	//下一位赋给当前值
	}
	return pre;
}

//2.递归法
ListNode* reverseList2(ListNode* head)
{
	if ( !head || !head->next)
		return head;
	ListNode *pNode = reverseList2(head->next);
	head->next->next = head;
	head->next = NULL;
	return pNode;
}

//main
int main()
{
	//创建链表
	ListNode* head = NULL;
	ListNode* cur = NULL;	//current
	for (int i = 1; i <= 6; ++i)
	{
		ListNode* node = new ListNode;
		node->val = i;
		node->next = NULL;
		if (head == NULL)
		{
			head = node;
			cur = node;
		}
		else
		{
			cur->next = node;
			cur = node;
		}
	}
	printList(head);	//打印当前链表
	printList(reverseList1(head));	//第一种方法
	//printList(reverseList2(head));	//第二种方法
	return 0;
}