Merge Two Sorted Lists

1-1. 접근법 (Iterative)

더미 노드를 사용해서 결과 리스트를 구성하면서 두 리스트를 순회하기

  • 더미노드를 만들어 시작점 설정
  • 두 리스트의 현재 노드 값을 비교
  • 더 작은 값을 결과 리스트에 연결
  • 해당 포인터를 다음으로 이동
  • 한 리스트가 끝나면 나머지를 모두 연결

1-2. Recursive 접근법

각 단계에서 더 작은 노드를 선택하고 나머지는 재귀 호출로 처리

  • Base Case: 한 리스트가 null이면 다른 리스트 반환
  • Recursive Case: 더 작은 노드의 next를 재귀 호출 결과로 설정
  1. Time-Complexity

O(m + n)

두 리스트의 모든 노드를 한 번씩 방문

// Definition for singly-linked list.
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        // Create a dummy node to simplify the logic
        let dummy = ListNode(0)
        var current = dummy
        
        var l1 = list1
        var l2 = list2
        
        // Compare nodes from both lists and add the smaller one
        while l1 != nil && l2 != nil {
            if l1!.val <= l2!.val {
                current.next = l1
                l1 = l1!.next
            } else {
                current.next = l2
                l2 = l2!.next
            }
            current = current.next!
        }
        
        // Add remaining nodes from either list
        if l1 != nil {
            current.next = l1
        } else {
            current.next = l2
        }
        
        return dummy.next
    }
}

// MARK: - Alternative Recursive Solution
class SolutionRecursive {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        // Base cases
        guard let l1 = list1 else { return list2 }
        guard let l2 = list2 else { return list1 }
        
        // Recursive case
        if l1.val <= l2.val {
            l1.next = mergeTwoLists(l1.next, l2)
            return l1
        } else {
            l2.next = mergeTwoLists(l1, l2.next)
            return l2
        }
    }
}

// MARK: - Helper functions for testing
extension ListNode {
    // Helper function to create a linked list from an array
    static func createList(from array: [Int]) -> ListNode? {
        guard !array.isEmpty else { return nil }
        
        let head = ListNode(array[0])
        var current = head
        
        for i in 1..<array.count {
            current.next = ListNode(array[i])
            current = current.next!
        }
        
        return head
    }
    
    // Helper function to convert linked list to array for easy printing
    func toArray() -> [Int] {
        var result: [Int] = []
        var current: ListNode? = self
        
        while current != nil {
            result.append(current!.val)
            current = current!.next
        }
        
        return result
    }
    
    // Helper function to print the linked list
    func printList() -> String {
        return toArray().map(String.init).joined(separator " -> ")
    }
}

// MARK: - Example Usage
func testMergeTwoLists() {
    let solution = Solution()
    
    // Test case 1: [1,2,4] and [1,3,4] -> [1,1,2,3,4,4]
    let list1 = ListNode.createList(from: [1, 2, 4])
    let list2 = ListNode.createList(from: [1, 3, 4])
    let merged1 = solution.mergeTwoLists(list1, list2)
    print("Test 1: \(merged1?.printList() ?? "empty")")
    
    // Test case 2: [] and [] -> []
    let merged2 = solution.mergeTwoLists(nil, nil)
    print("Test 2: \(merged2?.printList() ?? "empty")")
    
    // Test case 3: [] and [0] -> [0]
    let list3 = ListNode.createList(from: [0])
    let merged3 = solution.mergeTwoLists(nil, list3)
    print("Test 3: \(merged3?.printList() ?? "empty")")
    
    // Test case 4: [1,2,3] and [4,5,6] -> [1,2,3,4,5,6]
    let list4 = ListNode.createList(from: [1, 2, 3])
    let list5 = ListNode.createList(from: [4, 5, 6])
    let merged4 = solution.mergeTwoLists(list4, list5)
    print("Test 4: \(merged4?.printList() ?? "empty")")
}

// Run tests
testMergeTwoLists()

Best Time to Buy and Sell Stock

  1. My approach

Brute Force.

My code has a time complexity of O(n^2) because I am using nested loops - for each starting position. I checked all possible selling positions.

But there is a constraint of up to 10^5 elements. this approach will time out.

func maxProfit(_ prices: [Int]) -> Int {
        var start = 0
        var profit = 0
        while start < prices.count - 1 {
            for i in (start + 1..<prices.count) {
                let diff = prices[i] - prices[start]
                
                if profit < diff {
                    profit = diff
                }
            }

            start += 1
        }
        return profit
}

Solution

func maxProfit(_ prices: [Int]) -> Int {
    var minPrice = prices[0]    // Track the lowest price seen so far
    var maxprofit = 0    // Track the maximum profit achievable
    for i in 1..<prices.count {
        // Check if selling today gives us better profit
        maxProfit = max(maxprofit, prices[i] - minPrice)

        // Update minimum price if today's price is lower
        minPrice = min(minPrice, prices[i])
    }

    return maxProfit
}