206. Reverse Linked List

Problem

Reverse a singly linked list.

Example:

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:

Code

# 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

    print("None")

test_ll()

0=>1=>2=>3=>4=>None

Complexity

  • Time complexity is O(n)

Optimization

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