파이썬 알고리즘 인터뷰 - 15. 역순 연결 리스트

 

<--- 리트코드 206. Reverse Linked List --->

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

 

입력

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

출력

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

 

 

# 풀이

1. 재귀 구조로 뒤집기 

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def reverse_list(head):
  def reverse(node, prev=None):
    if not node:
      return prev
    next, node.next = node.next, prev
    return reverse(next, node)
    
  return reverse(head)
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
list5 = ListNode(5)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
list4.next = list5
 
head = reverse_list(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next

 

2. 반복 구조로 뒤집기

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def reverse_list(head):
  node, prev = head, None
 
  while node:
    next, node.next = node.next, prev
    prev, node = node, next
 
  return prev
 
list1 = ListNode(1)
list2 = ListNode(2)
list3 = ListNode(3)
list4 = ListNode(4)
list5 = ListNode(5)
 
head = list1
list1.next = list2
list2.next = list3
list3.next = list4
list4.next = list5
 
head = reverse_list(head)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next