【朱迪的LeetCode刷题笔记】】206. Reverse Linked List #Easy #Python #C++

Judie

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:
Input: head = [1,2]
Output: [2,1]

Example 3:
Input: head = []
Output: []


Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000

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


Judy
Python iterative version

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

https://leetcode.com/problems/re ... 3/python-recursive/
Solution 1
Python recursive version

class Solution:
    def reverseList(self, head: Optional[ListNode], prev = None) -> Optional[ListNode]:
        if head is None:
            return prev
        next = head.next
        head.next = prev
        return self.reverseList(next, head)
        ```

Mike
C++ iterative version

ListNode* reverseList(ListNode* head) {
        ListNode* current = head;
        ListNode* prev = nullptr;
        while (current != nullptr) {
            ListNode* temp = current->next;
            current->next = prev;
            prev = current;
            current = temp;
        }
        return prev;
    }

C++ recursive version

/**
 * 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* reverseLast(ListNode* head, ListNode* prev) {
        if (head->next == nullptr) {
            head->next = prev;
            return head;
        }
        ListNode* retval = reverseLast(head->next, head);
        head->next = prev;
        return retval;
    }
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr) {
            return head;
        }
        return reverseLast(head, nullptr);
    }
};