문제
leetcode.com/problems/reverse-linked-list/
Reverse Linked List - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
코드
1) 연결리스트의 값들을 스택에 순서대로 저장한 뒤, 맨 마지막에 저장된 값부터 차례대로 새로운 연결리스트에 저장
# 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:
if not head:
return head
# linked_list -> list
stack = []
while head is not None:
stack.append(head.val)
head = head.next
# list -> linked_list
result = ListNode()
for i,num in enumerate(stack[::-1]):
if i == 0 :
result.val = num
else :
node = result
while node.next != None:
node = node.next
node.next = ListNode(num)
return result
다른 코드
연결리스트는 재귀 또는 반복 구조로 뒤집을 수 있다.
1) 재귀 구조로 뒤집기
# 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):
if not node:
return prev
next, node.next = node.next, prev
return reverse(next, node)
return reverse(head)
2) 반복 구조로 뒤집기
# 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
'⏳ 알고리즘 > python 알고리즘 문제 풀이' 카테고리의 다른 글
리트코드 - 24. Swap Nodes in Pairs (0) | 2021.05.11 |
---|---|
리트코드 - 2. Add Two Numbers (0) | 2021.05.10 |
리트코드 - 21. Merge Two Sorted Lists (0) | 2021.05.09 |
리트코드 - 349. Intersection of Two Arrays (0) | 2021.05.07 |
프로그래머스 - LV3. 가장 긴 팰린드롬 (0) | 2021.05.02 |