Devin's Blog

Reverse Linked List

2 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • Keep proper track of the pointers. Specifically, creating a dummy node helps, and then take care that you always have a pointer for the next node.
  • Make sure you keep track of prev, cur, and future.

Code

Recursive Solution

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        def r(prev, cur):
            nonlocal head
            if not cur:
                return
            if not cur.next:
                head = cur
            r(cur, cur.next)
            cur.next = prev
        
        r(None, head)
        return head

Iterative Solution

With Dummy Node

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
 
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        itr = head
        future = head.next
 
        while future:
            itr.next = prev
            prev = itr
            itr = future
            future = future.next
 
        itr.next = prev
        head.next = None
        return itr

Without Dummy Node

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
 
        prev = None
        cur = head
        root = None
        while cur:
            nxt = cur.next
            if not nxt:
                root = cur
            cur.next = prev
            prev = cur
            cur = nxt
        return root

With Array

# 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: Optional[ListNode]) -> Optional[ListNode]:
        arr = []
        original_head = head
        while head:
            arr.insert(0, head.val)
            head = head.next
        
        head = original_head
        for val in arr:
            head.val = val
            head = head.next
            
        head = original_head
 
        return head

Notes

Cards

START Basic Front: Reverse Linked List - LeetCode Back: Use 3 variables if doing iteratively, making sure to save the last node. Tags:

END

References

Graph View

Backlinks