206. Reverse Linked List


Reverse a singly linked list.


Input: 1->2->3->4->5->NULL
Output: NULL<-1<-2<-3<-4<-5

Follow up:

  • A linked list can be reversed either iteratively or recursively. Could you implement both?

Thought Process

  • if to reverse a link list iteratively, need three pointers to store

    • pre => previous node
    • cur => current node
    • nxt => next node (here nxt is different from node’s own next reference)
  • Iterate thru ll, for any given state:

    • cur.next => pre
    • pre => cur
    • cur => nxt
    • nxt => nxt.next

White Board

Below is the white board:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head):

        pre = ListNode(None)
        cur = head

        while cur is not None: #O(n)
            # store the current next node
            nxt = cur.next

            cur.next = pre
            # reverse the node
            pre = cur
            cur = nxt
            nxt = cur.next

        # now cur is None, pre is the last node from the original ll
        # pre is the head node for the new ll
        return pre

def create_ll(nums):
    if len(nums) == 0:
        return None
    head = ListNode(nums[0])

    cur = head

    for num in nums[1:]:
        cur.next = ListNode(num)
        cur = cur.next

    return head

def test_ll():
    nums = list(range(5))

    curr = create_ll(nums)

    while curr is not None:
        print(curr.val, end="=>")
        curr = curr.next




  • Time complexity is O(n)


Will try to figure out a recursive solution in the future.