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

 

<--- 리트코드 92. Reverse Linked List Ⅱ --->

# 문제: 인덱스 m에서 n까지를 역순으로 만들어라. 인덱스 m은 1부터 시작한다.

 

입력

1->2->3->4->5->NULL, m = 2, n = 4

출력

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

 

 

# 풀이

1. 반복 구조로 노드 뒤집기

from typing import List
 
class ListNode(object):
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = None
 
def odd_even_list(head, m, n):
  if not head or m == n:
    return head
 
  root = start = ListNode(None)
  root.next = head
 
  for _ in range(m - 1):
    start = start.next
  end = start.next
 
  for _ in range(n - m):
    tmp, start.next, end.next = start.next, end.next, end.next.next
    start.next.next = tmp
  return root.next
 
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
 
m = 2
n = 4
head = odd_even_list(head, m, n)
 
while head:
  print(head.val, end="")
  if head.next:
    print("->", end="")
  head = head.next