연결리스트 문제
Floyd’s Cycle Detection Algorithm - 투포인터 문제
플로이드의 사이클 탐지 알고리즘이란 연결 리스트에서 사이클을 감지하는 문제에서 자주 사용되는 알고리즘으로 토끼와 거북이 알고리즘으로도 불린다. 두개의 포인터를 사용해서 리스트를 탐색하는데, 하나의 포인터는 거북이처럼 한칸씩 이동하고, 나머지 포인터는 토끼처럼 m칸씩 움직인다. (2칸) 만약 사이클이 없다면, 빠른 포인터는 끝(fast.next == null)에 도달하고, 사이클이 존재한다면 느린 포인터를 결국 따라잡게 된다. (slow == fast)
시간 복잡도 : O(n)
공간 복잡도 : O(1)
1) linked-list-cycle
문제 : https://leetcode.com/problems/linked-list-cycle/
class Solution {
fun hasCycle(head: ListNode?): Boolean {
if(head == null) {
return false
}
var slow: ListNode? = head.next
var fast : ListNode? = head.next?.next
var answer = false
while(true) {
if (fast == null) {
answer = false
break
}
if (fast == slow) {
answer = true
break
}
slow = slow?.next
fast = fast?.next?.next
}
return answer
}
}
class Solution {
fun hasCycle(head: ListNode?): Boolean {
var slow = head
var fast = head
while (fast != null && fast.next != null) {
slow = slow?.next
fast = fast.next?.next
if (slow == fast) return true
}
return false
}
}
2) remove-nth-node-from-end-of-list
문제 : https://leetcode.com/problems/remove-nth-node-from-end-of-list
class Solution {
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var fast: ListNode? = dummy
var slow: ListNode? = dummy
for(i in 0..n) {
fast = fast?.next
}
while(fast != null) {
fast = fast?.next
slow = slow?.next
}
slow?.next = slow?.next?.next
return dummy.next
}
}
3) reorder-list
문제 : https://leetcode.com/problems/reorder-list/
주어진 리스트를 노드의 값을 바꾸지 않고 제시된 순서대로 재정렬하는 문제다.
L0 → L1 → L2 → … → Ln-1 → Ln
➡️
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
1. 리스트를 중간에서 반으로 자르고, -> (TwoPointer 활용)
2. 후반부 리스트를 역순으로 정렬하고,
3. 반쪽 앞 리스트와 반쪽 뒤 리스트를 교차하면서 병합해야 한다.
class Solution {
fun reorderList(head: ListNode?): Unit {
if(head == null) {
return
}
// 중간 지점 찾기
var slow = head
var fast = head
while (fast?.next != null && fast?.next?.next != null) {
slow = slow?.next
fast = fast?.next?.next
}
// 뒤쪽 리스트 역순 정렬하기 + 중간에서 자르기
var second = reverse(slow?.next)
slow?.next = null
// 두 리스트 병합하기
var first = head
while(second != null) {
val tmp1 = first?.next
val tmp2 = second?.next
first?.next = second
second.next = tmp1
first = tmp1
second = tmp2
}
}
private fun reverse(head:ListNode?): ListNode? {
var prev: ListNode? = null
var curr = head
while (curr != null) {
val next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
}
merge-two-sorted-lists
문제 : https://leetcode.com/problems/merge-two-sorted-lists/
두개의 연결리스트에서 next를 변경해가면서 정렬하는 문제이다.
시간 복잡도 : O(n + m) → 리스트 길이의 합만큼 순회
공간 복잡도 : O(1) → in-place로 연결 (노드 새로 안 만듦)
class Solution {
fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
var l1 = list1
var l2 = list2
val dummy = ListNode(0)
var curr = dummy
while(l1 != null && l2 != null) {
if(l1.`val` <= l2.`val`) {
curr.next = l1
l1 = l1.next
}else {
curr.next = l2
l2 = l2.next
}
curr = curr.next!!
}
curr.next = l1 ?: l2
return dummy.next
}
}
merge-k-sorted-lists
문제 : https://leetcode.com/problems/merge-k-sorted-lists/
1. PriorityQueue를 활용하는 방법
시간 복잡도 : O(n log k)
공간 복잡도 : O(1) → in-place로 연결 (노드 새로 안 만듦)
class Solution {
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
// Priority Queue
val priorityQueue = PriorityQueue<ListNode>(Comparator { a, b -> a.`val` - b.`val`})
for(listNode in lists) {
listNode?.let {priorityQueue.offer(listNode)}
}
val dummy = ListNode(0)
var curr = dummy
var next = priorityQueue.poll()
while(next != null) {
curr.next = next
next.next?.let {priorityQueue.offer(it)}
curr = curr.next
next = priorityQueue.poll()
}
return dummy.next
}
}
2. Divide & Conquer를 활용하는 방법
두개씩 병합하면서 점점 줄여나가는 방식으로 merge sort와 유사하다. 각 단계에서 리스트의 개수는 절반씩 줄어들고 각 병합은 O(n) 시간 (= 두 리스트 길이의 합만큼) 소요된다. 병합 단계가 logK 개이므로 (이분) 총 시간 복잡도는 O(n logK) n: 총 노드 수, k: 리스트 개수)
시간 복잡도 : O(n log k)
공간 복잡도 : O(1) → in-place로 연결 (노드 새로 안 만듦)
class Solution {
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
// Divide & Conquer (분할정복)
if(lists.isEmpty()) return null
return mergeRange(lists, 0, lists.size-1)
}
private fun mergeRange(lists: Array<ListNode?>, left: Int, right: Int): ListNode? {
if(left == right) return lists[left]
val mid = (left + right) / 2
val l1 = mergeRange(lists, left, mid)
val l2 = mergeRange(lists, mid + 1, right)
return mergeTwoLists(l1, l2)
}
private fun mergeTwoLists(l1:ListNode?, l2:ListNode?):ListNode? {
val dummy = ListNode(0)
var curr = dummy
var a = l1
var b = l2
while(a != null && b != null) {
if(a.`val` <= b.`val`) {
curr.next = a
a = a.next
} else {
curr.next = b
b = b.next
}
curr = curr.next!!
}
curr.next = a ?: b
return dummy.next
}
}