C++实现翻转一个单链表

怎样翻转一个单链表？怎样用较少的次数翻转一个单链表？

• 首先来看看翻转一个链表的具体含义。
  
  下面来看一个具体的题目

翻转一个链表
输入: 1 2 3
输出: 3->2->1->null

这里提供三种解决方案

1. 用数组的形式创建一个单链表，然后按照数组的索引逆序进行反转。
2. 将原链表重新遍历，然后边遍历边用头插法建立一个新的单链表，然后输出这个新的单链表即可。
   我们知道建立单链表有两种方法。头插法建立的话输出和输入相反；尾插法的话输出和输入一致。
3. 在原链表的基础上直接翻转。这个过程中需要三个链表指针。

前面两种方法比较简单，只是涉及数组的简单应用和单链表的创建，这里就不再写代码。我们直接来看看第三种方式。
主要步骤：

1.创建三个结点：分别指向头结点A，头结点的下一个结点B和B的下一个结点C。
2.翻转时，将B的next指向A，然后三个结点往后挪一个。
–	–

A -> B -> C ->D -> E

A <- B 断开 C ->D -> E

先建立节点类

//结点类
class ListNode
{
public:
	int val;
	ListNode* next;
	ListNode(int val)
	{
		this->val = val;
		this->next = NULL;
	}
};

下面就是翻转链表类

class Solution 
{
public:
	ListNode* reverse(ListNode* head) 
	{
		if (head == nullptr)
			return nullptr;

		ListNode* pMove1 = head;			//记录当前节点
		ListNode* pMove2 = head->next;		//记录当前节点的下一个结点
		ListNode* pMove3;					//记录当前节点下一个结点的下一个结点
		//先处理头结点
		pMove1->next = nullptr;
		while (pMove2)		//有可能链表只有一个节点
		{
			pMove3 = pMove2->next;
			pMove2->next = pMove1;			//交换pMove1和pMove2
			if (!pMove3)
				break;
			pMove1 = pMove2;
			pMove2 = pMove3;
		}

		return 		pMove2 == nullptr ? pMove1 : pMove2;				//返回尾结点
	}
};

最后来测试下

int main()
{
	const int NUM = 4;
	int ary[NUM];
	ListNode* list_head = new ListNode(-1);				//创建头结点
	ListNode* last;
	ListNode* p = list_head;
	for (int i = 0; i < NUM; i++)
	{
		cin >> ary[i];
		last = new ListNode(i);
		p->next = last;
		p = last;
	}
	//开始翻转链表
	Solution solution;
	ListNode* pMove = solution.reverse(list_head);
	while (pMove->next)
	{
		cout << pMove->val << "->";
		pMove = pMove->next;
	}
	cout << "null" << endl;
	return 0;
}

结果如下

0 1 2 3
3->2->1->0->null

这种方法相比较于第一种和第二种的话，更加的节约空间。