0206. Reverse Linked List
Easy | Linked List + Two Pointer | 16 ms (98.94%), 15.4 MB (80.06%)
Source: LeetCode - Reverse Linked List GitHub: Solution / Performance
Given the head of a singly linked list, reverse the list, and return the reversed list.
Constraints:
The number of nodes in the list is the range
[0, 5000].-5000 <= Node.val <= 5000
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Input: head = [1,2]
Output: [2,1]
Input: head = []
Output: []We reverse the linked list by modifying the current node's next pointer to make it point to the previous node.
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# (base case)
if not head: return head
if not head.next: return head
# ==================================================
# Linked List (Iterative) =
# ==================================================
# time : O(n)
# space : O(1)
prev = None
while head:
# STORE next node for next iteration
tmp = head.next
# RE-ASSIGN next pointer to prev node
head.next = prev
# ASSIGN prev node to current node
prev = head
# MOVE current node to next node
head = tmp
return prev
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
# (base case)
if not head: return head
if not head.next: return head
# ==================================================
# Linked List (Recursive) =
# ==================================================
# time : O(n)
# space : O(n)
# 5-4-n
# 1-2-3-4(head)-5(node) ➜ 1-2-3-4=5 ➜ 1-2-3-4-n
#
# 5(node)-4-n 5-4-3 5-4-3-n
# 1-2-3(head)-4-n ➜ 1-2-3=4 ➜ 1-2-3-n
node = self.reverseList(head.next)
# recursion will stop at the last element since head.next == None
head.next.next = head
head.next = None
return node
class Solution {
/**
* @time : O(n)
* @space : O(1)
*/
public ListNode reverseList(ListNode head) {
if( head == null || head.next == null ) return head;
ListNode prev = null;
while( head != null ){
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
}
Last updated
Was this helpful?