[LeetCode] Challenge log 206

Posted on | Edited on |
206. Reverse Linked List

Basic linklist operation. It can be done either recursively or iteritively.

Reverse a singly linked list.

Example:

1
2
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?

Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Recursive
class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # reverse and return head and tail
        if not head or not head.next: return head
        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return newHead
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# iteratively
class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        tail = None
        while cur:
            nxt = cur.next
            cur.next = tail
            tail = cur
            cur = nxt
        return tail
0%