题目

解答

迭代

/**
 * Definition for singly-linked list.
 * 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* reverseList(ListNode* head) {
        if(!head) return nullptr;
        if(!head->next) return head;

        ListNode* node = head->next, *temp = nullptr;
        head->next = nullptr;
        while(node) {
            temp = node->next;
            node->next = head;
            head = node;
            node = temp;
        }

        return head;
    }
};

递归

/**
 * Definition for singly-linked list.
 * 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* helper(ListNode* node) {
		if(node->next == nullptr) {
			ListNode* new_head = new ListNode();
			new_head->next = node;
			return new_head;
		}
		
		ListNode* head = helper(node->next);
		node->next->next = node;
		node->next = nullptr;
		return head;
	}	

    ListNode* reverseList(ListNode* head) {
		if(head == nullptr) return nullptr;
		
		ListNode* new_head = helper(head);

		return new_head->next;
    }
};

复杂度

时间复杂度：O(n)

空间复杂度：O(1)