【朱迪的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

1. # Definition for singly-linked list.
   
2. # class ListNode(object):
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. class Solution(object):
   
7.     def reverseList(self, head):
   
8.         """
   
9.         :type head: ListNode
   
10.         :rtype: ListNode
    
11.         """
    
12.         prev = None
    
13.         curr = head
    
14.         while curr:
    
15.             temp = curr.next
    
16.             curr.next = prev
    
17.             prev = curr
    
18.             curr = temp
    
19.         return prev

复制代码

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

1. class Solution:
   
2.     def reverseList(self, head: Optional[ListNode], prev = None) -> Optional[ListNode]:
   
3.         if head is None:
   
4.             return prev
   
5.         next = head.next
   
6.         head.next = prev
   
7.         return self.reverseList(next, head)
   
8.         ```

复制代码

Mike
C++ iterative version

1. 
   
2. ListNode* reverseList(ListNode* head) {
   
3.         ListNode* current = head;
   
4.         ListNode* prev = nullptr;
   
5.         while (current != nullptr) {
   
6.             ListNode* temp = current->next;
   
7.             current->next = prev;
   
8.             prev = current;
   
9.             current = temp;
   
10.         }
    
11.         return prev;
    
12.     }
    

复制代码

C++ recursive version

1. 
   
2. /**
   
3. * Definition for singly-linked list.
   
4. * struct ListNode {
   
5. *     int val;
   
6. *     ListNode *next;
   
7. *     ListNode() : val(0), next(nullptr) {}
   
8. *     ListNode(int x) : val(x), next(nullptr) {}
   
9. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
   
10. * };
    
11. */
    
12. class Solution {
    
13. public:
    
14.     ListNode* reverseLast(ListNode* head, ListNode* prev) {
    
15.         if (head->next == nullptr) {
    
16.             head->next = prev;
    
17.             return head;
    
18.         }
    
19.         ListNode* retval = reverseLast(head->next, head);
    
20.         head->next = prev;
    
21.         return retval;
    
22.     }
    
23.     ListNode* reverseList(ListNode* head) {
    
24.         if (head == nullptr) {
    
25.             return head;
    
26.         }
    
27.         return reverseLast(head, nullptr);
    
28.     }
    
29. };
    

复制代码