【反转链表模板题+迭代+递归】LeetCode 206. Reverse Linked List

题目描述

知识点

反转链表

结果

见代码实现

实现

码前思考

1. 使用两种解法：递归 / 迭代 来解题。这两种方法都要掌握，虽然可能迭代更直接，但是很多难题里面用递归用得比较多！

代码实现

迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//反转链表模板题，设置pre和cur~
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* curr = head;
        ListNode* tmp;
        while(curr){
            tmp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = tmp;
        }
        return pre;
    }
};

递归⭐⭐⭐⭐⭐

方法二：递归算法实现反转。

1. 终止条件：head为空或者只有head一个节点的时候，返回head。

2. 递归实现：把链表看成两个“节点”，第一个节点是head，第二个节点是剩余部分，将这两个节点完成反转。妙啊，看成两个部分，这样就能体现递归分解问题的思想了！！！
   

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* newHead;
    ListNode* reverseList(ListNode* head) {
        reserve(NULL,head);
        return newHead;
    }

    //不断地递归操作
    void reserve(ListNode* pre,ListNode* curr){
        if(curr == NULL){
            newHead = pre;
            return;
        }else{
            ListNode* next = curr->next;
            curr->next = pre;
            reserve(curr,next);
            return;
        }
    }
};

码后反思

1. 其实递归写法不是我那样写的(/≧▽≦)/，应该是下面这样写哒：
   

   /**
    * 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 || !head->next){//到达了最后的结点
               return head;
           }else{
               ListNode* p = reverseList(head->next);
               head->next->next = head;
               head->next = NULL;  //一定要设置为NULL!不然会出问题
               //printf("%d\n",head->val);
               return p;
           }
       }
   };