Leetcode-Problems/ReverseLinkedList.py at main · nafizcodes/Leetcode-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

## ITERATIVE
#Time complexity = O(n)   , Space Complexity = O(1)
 #if temp = head
# class Solution:
#     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
#         #itertive solution
#         prev = None

#         while head:
#             temp = head
#             head = head.next
#             temp.next = prev
#             prev = temp

#         return prev


 # if temp  = head.next

# class Solution:
#     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

#         prev = None

#         while head:
#             temp = head.next
#             head.next = prev
#             prev = head
#             head = temp

#         return prev


## RECURSION
#Time complexity = O(n)   , Space Complexity = O(n)

class Solution:
    # @param {ListNode} head
    # @return {ListNode}

    def reverseList(self, head):
        return self.reverse(head)

    def reverse(self, head, prev=None):

    # if the node if empty return None which is prev
        if not head:
            return prev

      #if temp is head.next
        # temp = head.next
        # head.next = prev
        # prev = head
        # head = temp

      #if temp is head
        temp = head
        head = head.next
        temp.next = prev
        prev = temp

        return self.reverse(head, prev)