LeetCode #206 Reverse Linked List

Posted on | Post modified | In , , , , , , , , ,

Problem

Reverse a singly linked list.

Example

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

Solution1

Method: Iterative

Time Complexity: O(n)

Space Complexity: O(1)

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head

        cur = head.next
        dummy = ListNode(float('-inf'))
        dummy.next = head
        dummy.next.next = None

        while cur:
            tmp = cur.next
            cur.next = dummy.next
            dummy.next = cur
            cur = tmp
        
        return dummy.next

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, prev = head, None

        while cur:
            cur.next, prev, cur = prev, cur, cur.next

        return prev

Solution2

Method: Recursive

Time Complexity:

Space Complexity: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head, prev = None):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return prev
        
        curr = head.next
        head.next = prev

        return self.reverseList(curr, head)

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        node = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return node