Leetcode 문제
이번에 풀어볼 문제는 리트코드 19번 문제 Remove Nth Node From End of List 다.
우선 문제를 살펴보자.
리트코드 19번 문제 Remove Nth Node From End of List 링크
Reorder List - LeetCode
Can you solve this real interview question? Reorder List - You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2
leetcode.com
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000
문제 설명
문제를 간략히 살펴보자. 인풋으로 배열이 주어지는데 이 element들은 차례대로 linked list를 이루고 있다. 예를 들어 L0->L1->...->Ln-1->Ln 순으로 되어있다 (여기서 n은 배열의 element 개수다). 이때 linked list를 재배열하여 L0->Ln->L1->Ln-1 순으로 만들라는 것이다.
문제 예시 1번을 보면 인풋으로 1->2->3->4 라는 linked list가 주어졌다. 이때 list의 첫번째 위치한 1을 가장 앞에 그리고 바로 그 뒤에 list의 가장 뒤에 있는 4를 연결하라는 것이다. 이어서 list의 두번째 위치한 2를 위치시키고 마지막으로 list의 가장 뒤에서 두번째 있는 3을 연결시키라는 것이다. 쉽게 설명하면 linked list가 있을 때 가장 왼쪽에서 하나 그리고 가장 오른쪽에서 하나씩 떼어와 그 순서대로 새로운 배열을 만들라는 것이다. 이제 문제를 풀어보도록 하자.
문제 접근법
이 문제를 해결하기 위해서 우리는 두 개의 포인터 (slow and fast)를 이용할 것이다.
여기서 slow 포인터는 한 칸씩 움직일 때 fast 포인터는 두 칸씩 움직인다.
따라서 두 포인터 모두 첫번째 노드에서 시작하면 fast 포인터가 마지막 노드에 도착했을 때 slow 포인터는 linked list의 가운에 위치한 노드에 도달하게 된다.
구체적으로 우리는 다음과 같은 과정을 통해 문제를 해결할 것이다.
1) Slow and fast 두 개의 포인터를 이용하여 linked list의 가운데 지점을 찾는다.
2) 가운데 지점의 오른쪽 반에 해당하는 노드들을 역순으로 배열한다.
3) 마지막으로 가운데 지점 왼쪽 반에 해당하는 노드와 역순으로 배열된 오른쪽 노드를 합한다. 이때 가장 앞에 위치한 노드들을 하나씩 가져와 서로 합친다.
이해를 돕기위해 예시를 들어 설명하겠다.
문제 예시 2번을 살펴보면 인풋으로 1->2->3->4->5라는 linked list가 주어졌다.
우리는 두 개의 포인터를 노드 1에서 출발시키면 다음과 같은 과정을 거친다.
Step1: Slow - node 1, Fast - node 1
Step2: Slow - node 2, Fast - node 3
Step3: Slow - node 3, Fast - node 5
Step4: Slow - node 4, Fast - None
네번째 과정에서 fast 포인터는 linked list를 벗어나게 된다.
따라서 slow 포인터가 위치한 node 4 가 가운데 지점이 된다.
앞서 설명한대로 4로부터 오른쪽 반을 역순으로 바꾸면 1->2->3 과 5->4라는 linked list가 얻어진다.
이제 두 linked list를 합칠것인데 각 list에서 하나씩 가져오면 1->5->2->4->3과 같이 된다.
이제 코드로 한 번 살펴보자.
문제 풀이
Linked list를 표현하기 위한 class를 선언해준다. (line 1-4)
이는 파이썬에서 일반적으로 사용되는 표현식이니 익숙해지도록 하자.
인풋 배열을 입력받기 위한 함수를 정의해 준다. (line 6)
만약 입력받은 인풋 배열이 비어있다면 아무것도 리턴하지 않고 종료한다. (line 7-8)
첫번째로 slow and fast 두 개의 포인터를 만들어 linked list 헤드에 위치시킨다. (line 11)
Fast 와 fast 포인터가 가리키는 다음 노드가 존재하는한 slow 포인터는 한 칸씩, fast 포인터는 두 칸씩 이동시킨다. (line 12-14)
이 과정을 마치고 나면 slow 포인터가 가리키고 있는 곳이 linked list의 가운데 지점이다.
두번째로 linked list의 가운데 지점으로부터 오른쪽 반을 역순으로 배열한다.
먼저 slow 포인터가 가리키는 곳을 curr로 그 전을 prev로 초기화를 시켜준다. (line 17)
이제 오른쪽 반을 역순으로 배열하는데 이해를 돕기 위해 위에서 설명한 4->5를 5->4로 바꾸를 과정을 설명하겠다.
우선 초기화를 통해 (prev) -> 4 (curr) -> 5 로 된다.
그 다음 과정은 5를 temp 변수에 넣어두고 curr 다음을 4로 만든다음 curr에 5를 넣어주는 과정이다. (line 18-22)
Iteration 예시
첫번째 iteration에서는 다음과 같이 진행된다.
next_temp = curr (=4)의 다음인 5
curr.next = curr (=4)의 다음은 none (=prev)
prev = 4
curr = 5
이 과정을 마치고 나면 4->None과 5가 얻어진다.
두번째 iteration에서는 다음과 같이 진행된다.
next_temp = curr (=5)의 다음인 none
curr.next = 4 (=prev)
prev = 5
curr = none
이 과정을 마치고 나면 5->4가 얻어진다.
이 과정이 조금 헷갈릴 수 있는데 각 변수에 숫자를 직접 넣어가며 생각해면 이해에 도움이 될 것이다.
마지막으로 두 linked list를 합치는 작업을 할 것이다.
우선 first and second 포인터를 각 linked list의 처음에 위치시킨다. (line 25)
예를 들어 1->2->3 과 5->4의 경우 first and second 포인터가 각각 1과 5를 가리키고 있다.
각 linked list에서 가장 처음에 위치한 노드 바로 다음 노드를 가져와 임시 변수에 넣어둔다. (line 27)
이 경우 임시 변수에 2와 4가 들어간다.
First 포인터가 가리키는 노드 다음을 second 포인터가 가리키는 노드와 연결한다. (line 28)
이 경우 1->5가 연결된다.
그 다음으로 second 포인터가 가리키는 노드 다음을 임시변수 1에 넣어놓은 노드와 연결시킨다.
이 경우 5->2가 되어 전체적으로 1->5->2 가 된다.
마지막으로 first and second 포인터에 임시변수 1, 2에 해당하는 노드로 이동시켜준다.
이 경우 first and second 포인터가 각각 2와 4를 가리킨다.
이 과정을 한 번 더 반복하고 나면 1->5->2 이후에 4와 3이 연결되어 1->5->2->4->3이 된다.
문제 풀이 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
if not head:
return
# Step 1: Find the middle of the linked list
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half of the list
prev, curr = None, slow
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
# Step 3: Merge the two halves
first, second = head, prev
while second.next:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2
# Helper function to print the list
def printList(node):
while node:
print(node.val, end=" ")
node = node.next
print()
# Example usage
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
reorderList(head)
printList(head) # Output should be 1 4 2 3
|
cs |
관련 문제
리트코드 19번 Remove Nth node from end of list 문제 풀이 (링크)
리트코드 21번 Merge two sorted lists 문제 풀이 (링크)
리트코드 23번 Merge K sorted lists 문제 풀이 (링크)
리트코드 141번 Detec cycle in a linked list 문제 풀이 (링크)
리트코드 206번 Reverse a linked list 문제 풀이 (링크)
