leetcode 206. 反转链表

题目:206. 反转链表

206. 反转链表

难度简单

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

迭代

1. 找到当前节点的下一个节点。
2. 当前指针指向前指针。
3. 前指针移动到当前指针
4. 当前指针向后移
5. 从步骤1到步骤4重复操作即可。

递归

递归的方法就是将自己的下一个节点作为参数传递，找到最后一个节点返回出来。

只要不是最后一个节点的，就翻转自己与下一个节点的指向。 例如a->b 变成a<-b。

实在是懒得画图了。

代码

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

class Solution {
public:
	ListNode* reverseList1(ListNode* head) {
		// 没有节点 和 只有一个节点不需要翻转
		if (!head || !head->next) return head;
		ListNode* pre = NULL, *curNode=head, *nextNode = head->next;
		while (curNode) {
			nextNode = curNode->next;
			curNode->next = pre;
			pre = curNode;
			curNode = nextNode;
		}
		return pre;
	}
	ListNode* reverseList(ListNode* head) {
		// 找到末尾指针
		if (!head || !head->next) return head;
		ListNode* Node = NULL;
		Node = reverseList(head->next);
		// 将自己的下一个节点的下一个节点指向自己，相当于链表指针翻转
		head->next->next = head;
		// 因为方向已经翻转，自己原来的指针应该断开
		head->next = NULL;
		return Node;
	}
};


#define SIZE_TEST 4
int main()
{
	ListNode* head0 = new ListNode(0);
	ListNode* head = head0;
	srand(time(NULL));
	for (int i = 0; i < SIZE_TEST; i++)
	{
		ListNode* mNode = new ListNode(i + 1);
		head0->next = mNode;
		head0 = head0->next;
	}

	Solution sln;
	ListNode*res = sln.reverseList(head);
	while (res != NULL)
	{
		cout << res->val << " ";
		res = res->next;
	}
	return 0;
}