🎯 leetcode - 92. Reverse Linked List II
🤔 나의 풀이
📌 문제
- 파이썬 알고리즘 인터뷰 19번 문제
- 연결리스트의 인덱스 m~n까지를 역순으로 만들어라. 📌 날짜
2020.01.28~29📌 시도 횟수
10 try+ / 이틀 고민해서 결국! 풀어냈지만 풀이가 너무 구닥다리니까 예쁜 풀이로 다시 풀어보자~💡 Code
class Solution:
def reverseList(self, head: ListNode):
root, node, prev = head, head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev, root # reversed List 처음, 끝 반환
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# root = start를 해준뒤에 start를 움직여야지 제대로 작동함
root = start = ListNode(0)
root.next = head
# 예외 처리
if not head or m == n:
return head
for i in range(1, m):
start = start.next # start = 1
end = start.next # 2
# 뒤집을 대상 linked list 만들기
new_root = node = ListNode()
for i in range(n - m + 1):
node.next = ListNode(end.val)
end = end.next
node = node.next
# 뒤집힌 대상 linkedlist의 처음, 끝 노드 반환
check_n, check_m = self.reverseList(new_root.next)
# 기존의 linked list 중간 끊어내고 뒤집은 linked list로 바꿔치기
start.next = check_n
check_m.next = end
# root의 첫번째는 dummy(val=0인)이므로 root.next 반환
return root.next💡 문제 해결 방법
☆15번째 문제 15.reverse Linked List에서 역순 링크드 리스트를 만드는 방법을 활용했다☆
1. 먼저 m~n번쨰 노드들로 이루어진 새로운 링크드리스트를 따로 만든다.
2. 그리고 이 링크드리스트의 head(루트)를 역순링크드리스트 만드는 함수에 넘긴다.
>> (def reverseList(self, head: ListNode):)로 head를 넘김
3. 참고로 넘기기 전에 이 부분 역순 링크드 리스트를 연결하기 위해 해당 링크드 리스트의 앞, 뒤 노드를 미리 찾아논다.
>> ex. [1, 2, 3, 4, 5]에서 m=2, n=4라고 하면 start = 1, end = 5이다.
>> 위의 코드에서는 start, end가 역순 링크드리스트의 앞, 뒤 노드이다.
4. 역순 링크드리스트의 반환값을 살짝 변형했다. 변환한 역순 링크드 리스트의 처음, 끝을 차례대로 반환했다.
5. 이렇게 부분 역순 링크드리스트의 처음, 끝을 각각 check_n, check_m에 받았다.
>> ex. [1, 2, 3, 4, 5]에서 m=2, n=4라고 하면...
>> self.reverseList(new_root.next)의 반환값은 각각 4, 2이다.
>> 따라서 check_m = 4, check_n = 2이다.
6. 이제 start, end와 check_n, check_m을 차례대로 연결해준다.
start.next = check_n이고, check_n.next = end이다.
>> ex. [1, 2, 3, 4, 5]에서 m=2, n=4라고 하면...
>> start = 1 ---> check_m = 4
>> check_n = 2 ---> end = 5
7. root.next를 반환한다.
따라서 최종적으로 1 -> 4 -> 3 -> 2 -> 5가 된다~💡 새롭게 알게 된 점
- m~n번쨰 노드들로 이루어진 새로운 링크드리스트를 따로 만들었다는 점이 좀 비효율적인 것 같다.❌ (한번에 맞추지 못한 경우) 오답의 원인
1. root 설정 오류! (이부분! ↓ ↓ ↓)
----------------------------
root = start = ListNode(0)
root.next = head
----------------------------
- 처음에는 그냥 root = head라고 해주었더니 처음부터 reversed 된 경우를 적용하지 못했다ㅠ
- 따라서 실제로 이동시킬 start에 root를 연결해야 (m = 1, n = 1보다 큰 수)인 경우를 제대로 reverse 할 수 있다.
2. 예외 처리 안함
----------------------------
if not head or m == n:
return head
----------------------------
- 이 부분이 생각보다 골칫거리였다ㅠ
- 그냥 코드 처음부터 예외로 처리해주니까 얼마나 편한가~~😵
😉 다른 풀이
📌 하나. 반복 구조로 뒤집기💯
내 코드 15줄을 거의 5줄로 줄였다...
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# 예외 처리
if not head or m == n:
return head
root = start = ListNode(0)
root.next = head
# start, end 지정
for _ in range(1, m):
start = start.next
end = start.next
# 반복하면서 노드 차례대로 뒤집기
for _ in range(n-m):
temp = start.next
start.next = end.next
end.next = end.next.next
start.next.next = temp
return root.next
문제 해결 방법
- start, end는 끝까지 값이 변하지 않는 점을 이해하자.
- 변하는 것은 start와 end가 가리키는 대상이다.
- 이때 temp는 현재 역순으로 바뀐 값들 중 맨 앞에 위치하고 있는 값이다.
- 즉 temp만 계속해서 갱신될 뿐, start와 end는 변하지 않고 각각이 가리키는 대상만 변한다.
1. 일단 세팅을 다 해논다. (m위치에 있는 값이 start, m+1위치에 있는 값이 end)
>> 참고로 end는 인덱스가 n인 위치로 한칸씩 한칸씩 이동할 것이다.
2. 우리가 역순으로 바꿔야 할 부분은 인덱스가 m ~ n인 부분이다.
3. 따라서 역순으로 바꿔야 할 부분의 처음을 항상 temp로 설정한다.
(temp의 갱신이 m-n번 실행되면 end는 최종적으로 인덱스 n의 위치가 된다.)
4. 이제 이 temp 앞으로 end.next를 가져올 것이다.
---------------------------------------------------
* 예시로 이해해보자
ex. 1 -> 2 -> 3 -> 4 -> 5 (m=2, n=4라고 가정하자.)
[현재 1회]
- start = 2, end = 3, temp = 2
- 역순 맨 앞에 end.next를 가져온다.
=> 1 -> "3" -> 2 -> 4 -> 5
[현재 2회]
- start = 2, end = 2, temp = 3
- 역순 맨 앞에 end.next를 가져온다.
=> 1 -> "4" -> 3 -> 2 -> 5
-> 최종적으로 (m-n)번 갱신한 결과, end이 인덱스 n의 위치로 이동했다!
---------------------------------------------------
5. temp 앞으로 end.next를 가져오기 위해...
(1) 일단 현재 temp = start.next(맨 앞)
(2) start.next = end.next (맨 앞으로 end.next 끌어오기)
(3) end.next = end.next.next (원래 end 위치를 end.next와 바꿈)
(4) start.next.next = temp (역방향 연결)👀 눈으로 보면 더 이해가 잘된다 🍡
- 으아 머리로 생각하려니까 너무 복잡하다.
- 다시 풀어보면서 익숙해지자. 머리도 좀 빨리빨리 굴리고..💡 새롭게 알게 된 점
- 
열심히💨 (알고리즘 블로그)