leetcode 206. 反转链表

大耗子 2021年02月19日 14次浏览

题目: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;
}