Recursion
Linked List
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
Python3 Java C++ Go TypeScript Rust JavaScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 # 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 /**
* 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 /**
* 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 ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 // 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
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* 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 ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 /**
* 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 pre = null ;
for ( ListNode p = head ; p != null ;)
{
ListNode t = p . next ;
p . next = pre ;
pre = p ;
p = t ;
}
return pre ;
}
}
Solution 2
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13 # 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 /**
* 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 /**
* 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 /**
* 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 /**
* 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 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 // 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 )
}
}