연결리스트 문제

 

 

 

 

 

Floyd’s Cycle Detection Algorithm - 투포인터 문제 

 

https://medium.com/swlh/floyds-cycle-detection-algorithm-32881d8eaee1

 

플로이드의 사이클 탐지 알고리즘이란 연결 리스트에서 사이클을 감지하는 문제에서 자주 사용되는 알고리즘으로 토끼와 거북이 알고리즘으로도 불린다. 두개의 포인터를 사용해서 리스트를 탐색하는데, 하나의 포인터는 거북이처럼 한칸씩 이동하고, 나머지 포인터는 토끼처럼 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
    }
}