【朱迪的LeetCode刷题笔记】】206. Reverse Linked List #Easy #Python #C++
本帖最后由 Judie 于 2023-5-29 21:03 编辑Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head =
Output:
Example 2:
Input: head =
Output:
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range .
-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/reverse-linked-list/solutions/2123063/python-recursive/
Solution 1
Python recursive version
class Solution:
def reverseList(self, head: Optional, prev = None) -> Optional:
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);
}
};
页:
[1]