[LeetCode]Reverse Linked List

这道题有递推和循环两个做法。递归的做法很直观，我们递归第reverse当前节点右边的linkedlist，返回的时候把当前节点加到新linkedlist的尾巴即可。时间复杂度O(N)，空间复杂度O(N)，递归深度。代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseList(ListNode* head) {
	return reverse(head);
	}
	private:
	ListNode* reverse(ListNode* head)
	{
	if(!head || !head->next)return head;
	ListNode* tail = head->next;
	ListNode* newHead = reverse(head->next);
	tail->next = head;
	head->next = nullptr;
	return newHead;
	}
	};

view raw Reverse Linked List_recursion.cpp hosted with ❤ by GitHub

循环的做法就是维护两个指针，每一次翻转两个节点一直到末尾即可。时间复杂度O(N)，常数空间。代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseList(ListNode* head) {
	if(!head)return head;
	ListNode* curr = head->next, *prev = head;
	prev->next = nullptr;
	while(curr)
	{
	ListNode* tmp = curr->next;
	curr->next = prev;
	prev = curr;
	curr = tmp;
	}
	return prev;
	}
	};

view raw Reverse Linked List_iteration.cpp hosted with ❤ by GitHub