[leetcode]206 연결리스트 뒤집기

https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

문제 : 단일 연결 리스트를 뒤집어라.

 

입력 : 1 ->2 ->3->4->5->NULL

 

출력 : 5->4->3->2->1->NULL

 

1. 나의 풀이 방법

 

1. 연결리스트를 리스트로 변환한다.

2. reverse() 함수를 사용하여 리스트를 뒤집어준다.

3. 리스트를 다시 연결리스트로 만들어주기.

 

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def reverseList(self, head):
        #1번 리스트에 다 넣고 reverse()함수를 통해 재정렬 -> 다시 연결리스트로 만들어주기

        #연결리스트 -> 리스트

        if head is None:
            return
        arr =[]
        while head is not None:
            arr.append(head.val)
            head=head.next
        #리스트를 뒤집기
        arr.reverse()

        #리스트를 연결리스트로

        if len(arr)>0:
            head_node = ListNode(arr[0])
            current = head_node

            for i in range(1,len(arr)):
                new_node = ListNode(arr[i])
                current.next = new_node
                current = current.next
            
        return head_node

 

시간복잡도 : O(n) , 공간복잡도 O(n)