Description
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?
Solutions
Solution 1: Head Insertion Method
We create a dummy node dummy, then traverse the linked list and insert each node after the dummy node. After traversal, return dummy.next.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScriptC#
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
dummy = ListNode()
curr = head
while curr:
next = curr.next
curr.next = dummy.next
dummy.next = curr
curr = next
return dummy.next(code-box)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}(code-box)
/**
* 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) {
ListNode* dummy = new ListNode();
ListNode* curr = head;
while (curr) {
ListNode* next = curr->next;
curr->next = dummy->next;
dummy->next = curr;
curr = next;
}
return dummy->next;
}
};(code-box)
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
dummy := &ListNode{}
curr := head
for curr != nil {
next := curr.Next
curr.Next = dummy.Next
dummy.Next = curr
curr = next
}
return dummy.Next
}(code-box)
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
let pre = null;
let cur = head;
while (cur != null) {
const next = cur.next;
cur.next = pre;
[pre, cur] = [cur, next];
}
return pre;
}(code-box)
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut head = head;
let mut pre = None;
while let Some(mut node) = head {
head = node.next.take();
node.next = pre.take();
pre = Some(node);
}
pre
}
}(code-box)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let dummy = new ListNode();
let curr = head;
while (curr) {
let next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
};(code-box)
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}(code-box)
Solution 2: Recursion
We recursively reverse all nodes from the second node to the end of the list, then attach the head to the end of the reversed list.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the linked list.
PythonJavaC++GoTypeScriptRustC#
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
ans = self.reverseList(head.next)
head.next.next = head
head.next = None
return ans(code-box)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode ans = reverseList(head.next);
head.next.next = head;
head.next = null;
return ans;
}
}(code-box)
/**
* 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 || !head->next) return head;
ListNode* ans = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return ans;
}
};(code-box)
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
ans := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return ans
}(code-box)
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
const rev = (pre: ListNode | null, cur: ListNode | null): ListNode | null => {
if (cur == null) {
return pre;
}
const next = cur.next;
cur.next = pre;
return rev(cur, next);
};
function reverseList(head: ListNode | null): ListNode | null {
if (head == null) {
return head;
}
const next = head.next;
head.next = null;
return rev(head, next);
}(code-box)
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
fn rev(pre: Option<Box<ListNode>>, cur: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
match cur {
None => pre,
Some(mut node) => {
let next = node.next;
node.next = pre;
Self::rev(Some(node), next)
}
}
}
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
Self::rev(None, head)
}
}(code-box)
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode ans = ReverseList(head.next);
head.next.next = head;
head.next = null;
return ans;
}
}(code-box)
