hey everyoneđź‘‹
Today We discuss the leetcode #206 problem
Problem
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution — Iteration-
Use a pointer that points to a node x which is head at beginning. In each iteration if it has next node y ,move next node to be front of current head and update head pointer to y. Once x has not next node, i.e. it’s tail, end the iteration.
# Python3
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# Iteration approach
# Run one pointer p in list. At each iteration:
# 1. n = p.next
# 2. p.next = n.next, jump cross n
# 3. n.next = head, n prepend to the front
# 4. head = n, reassign head
if head == None:
return None
p = head
while p.next:
n = p.next
p.next = n.next
n.next = head
head = n
return head
Complexity-
the time complexity is O(n) if n denotes to counts of nodes in this linked list.
It’s trivial that it only uses O(1) extra space.
Solution — Recursion
# Python3
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# Recursion approach:
# take head and reverse list whose head is head.next
# then reversely assign the link between them
if head == None or head.next == None:
return head
n = head.next
h = self.reverseList(n)
# reverse link
head.next = None
n.next = head
return h
Complexity
At each function call, it’s only takes** O(1) time for assigning link**. And there are n-2 calls if n denotes to counts of nodes in this linked list. Therefore, time complexity will be O(n).
Also, it **uses O(1) extra space **in each function call and there are n-2 calls in calling stack. Hence space complexity is O(n) as well.
Thank you for read this article .I hope its help you to solve this problem
If you like the article so just follow on *@coders_village in instagram *
Thank You
Shivani Tiwari
(Software Developers)
Top comments (0)