LeetCode. Reverse Linked List [Linked List]

Problem:

Reverse a singly linked list.

 

Example:

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

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

 

-Summary-

1. Keep track of current / prev (copy the original list in the curr and prev)

2. Update and move the head (original)

3. Return prev

 

-Other iterative solution-

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev

-Recursive solution-

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(node: ListNode, prev: ListNode = None) -> ListNode:
            
            if not node:
                return prev
            
            next, node.next = node.next, prev
            
            return reverse(next,node)
            
        return reverse(head)

 

정답을 보니 recursive 하게 푸는 방법도 있었다. 

leetcode.com/problems/reverse-linked-list/discuss/609282/Python-Recursion-Highly-Commented-(greater99)

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]