Leetcode206.反转链表

题目

反转一个单链表。

示例:

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

代码

法一、迭代法

 1 class Solution {
 2 public:
 3     ListNode* reverseList(ListNode* head) {
 4         ListNode* pre = NULL; ListNode* cur = head;
 5         // pre 前指针,cur 当前指针, tmp 保存当前指针后一个
 6         while(cur != NULL  ){
 7             ListNode* tmp = cur->next;
 8             cur->next = pre;
 9             pre = cur;  //前指针后移
10             cur = tmp;  //当前指针后移
11     }
12     return pre;
13     }
14 };

这种方法开始画个图理解，比如举只有两个节点的链表，找到规律：修改当前指针指向前节点，前指针后移，当前指针后移。

不断的循环此步骤，但是当前指针指向前面节点时，当前指针如何更新后移？所以还需要一个指针保存当前指针的下一个节点。

时间复杂度 O(n)，空间复杂度O(1)

法二、递归（尾递归）。。.有些不好理解

 1 class Solution {
 2 public:
 3     ListNode* reverseList(ListNode* head) {
 4         if(head == NULL || head->next == NULL ) return head;
 5         ListNode*p =  reverseList(head->next);
 6         head->next->next = head;
 7         head->next = NULL;  //a1节点指向空
 8         return p;
 9     }
10 };

时间复杂度O（n），空间复杂度O(n)——隐式栈空间