[每日 LeetCode] 206. Reverse Linked List

Description:

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

思路：本题要求反转链表。分为迭代方法和递归方法。

迭代方法：采用头插法思想，从头结点开始依次进行头插操作，最后返回新链表。

递归方法：比较难理解，重要的是需要在第一次返回后修改节点指针，使其指向剩余为输出节点。

C++ 代码（迭代）

/**
 * 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) {
        ListNode* newlist = nullptr;
        while(head){
            ListNode* temp = head;
            head = head->next;
            temp->next = newlist;
            newlist = temp;
        }
        return newlist;
    }
};

运行时间：8ms

运行内存：9.2M

C++ 代码（递归）

/**
 * 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 == NULL || head->next == NULL)
            return head;
        
        ListNode* base = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return base;
    }
};

运行时间：8ms

运行时间：9.3M