문제링크: https://leetcode.com/problems/reverse-linked-list-ii
역순 연결리스트를 만드는 건데 전부는 아니고 정해진 구간에서만 역순으로 만들어야한다.
전부 역순 만드는 문제: https://leetcode.com/problems/reverse-linked-list
발상은
역순으로 만들어야 하는 부분의 앞부분을 1(first)
역순으로 만들어야 하는 부분을 2(second)
역순으로 만들어야 하는 부분의 뒷부분을 3(third)
으로 따로 만든 후 1,2,3 한방에 연결.
pointer = head
second = ListNode(None)나중에 1,2,3을 이어붙이려면 first의 마지막노드, second의 처음노드, second의 마지막노드, third의 처음노드를 알아야지 이어붙이니까
(ex. first_tail.next = second_head
second_tail.next = third_head ) ------(1)
pointer로 head를 훑으면서 하나씩 뽑아내자
second = ListNode(None)을 한 이유는 역순으로 만들고자 하는 의지이다.
n = 1
while n <= right:
if n < left - 1:
pointer = pointer.next
n += 1
elif n == left - 1:
first_tail = pointer
pointer = pointer.next
n += 1
elif n == left:
second, second.next, pointer = pointer, second, pointer.next
second_tail = second
n += 1
else:
second, second.next, pointer = pointer, second, pointer.next
n += 1학교에서 집을 가는데 가는길에 떡볶이도 먹고 책도 사는 것처럼 pointer가 right번 next하면서 가는 길에 first_tail, second_tail을 챙기는 것이다.
아까 주머니에 묵혀놨던 second=ListNode(None)을 꺼내서 다중할당으로 역순부분을 만들었다.이 다중할당 패턴은 역순나올때마다 자주쓰이는 패턴인 것 같아서 익혀두면 나쁘지 않을듯하다.
그리고 while이 다 돌면 결국 pointer가 third_head가 된다.
first_tail.next = second
second_tail.next = pointer
return head이렇게 while문 돌린 후 이어 붙여주자.
그리고 내 처음 발상과 문제의 조건을 비교했을 때 다른 부분을 찾아보면 이 문제의 조건들중
1 <= left <= right <= n이 있다.
이처럼 left는 1이 될 수 있으므로 처음 발상대로 first가 항상 존재하는 건 아니다.
따라서
if left == 1:
second_tail.next = pointer
return second이렇게 first가 없을 때는 second와 third만 이어붙여서 예외처리를 하자
(또한 left와 right는 같을 수도 있어서 second가 항상 존재하는 게 아니고 right가 n까지 갈 수도 있어서 third도 항상 존재하는 건 아니지만 그 예외처리는 하지 않아도 잘 걸러진다.)
그래서 전체코드는
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
pointer = head
second = ListNode(None)
#n은 실행횟수
n = 1
while n <= right:
if n < left - 1:
pointer = pointer.next
n += 1
elif n == left - 1:
first_tail = pointer
pointer = pointer.next
n += 1
elif n == left:
second, second.next, pointer = pointer, second, pointer.next
second_tail = second
n += 1
else:
second, second.next, pointer = pointer, second, pointer.next
n += 1
#while문 종료되면 pointer는 third_head가 됨
#예외처리 second와 third만 이어붙이기
if left == 1:
second_tail.next = pointer
return second
#first, second, third 이어붙이기
first_tail.next = second
second_tail.next = pointer
return head'파이썬 알고리즘 인터뷰'에서는
#예외 처리
if not head or left == right:
return head
root = start = ListNode(None)
root.next = head
#start, end 지정
for _ in range(left - 1):
start = start.next
end = start.next
#반복하면서 노드 차례대로 뒤집기
for _ in range(right - left):
tmp, start.next, end.next = start.next, end.next, end.next.next
start.next.next = tmp
return root.next
내 풀이랑 비교하면 나는 중간부분을 처음부터 자른다음에 나중에 한번에 이어붙인거고 이 책에서의 풀이는 중간부분을 차례차례 역순으로 만들면서 이어붙인것이다.
그래서 나는 알아야될 노드들이 많았고(first_tail이나 second_head같은)
이 풀이는 굳이 그런 노드들을 알 필요가 없는 것이다.
