[LeetCode/Swift] 876. Middle of the Linked List

💡 문제 (Easy)

Middle of the Linked List - LeetCode

Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
주어진 단일 연결 리스트의 헤드가 주어졌을 때, 해당 연결 리스트의 중간 노드를 반환하세요.
만약 중간 노드가 두 개인 경우, 두 번째 중간 노드를 반환하세요.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

 

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

 

Constraints:

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

👩🏻‍💻 해결

/**
 * 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; }
 * }
 */

 

1차 : array 활용 방법 사용

array를 생성하여 ListNode를 각각 인덱스에 맞게 넣어주고 2로 나누어 중간 값을 반환하는 방법 사용

시간 복잡도 O(n) 공간 복잡도 O(n)

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var array: [ListNode?] = []
        var node: ListNode? = head
        
        while(node != nil) {
            array.append(node)
            node = node?.next
        }
        
        return array[array.count/2]
    }
}

 

2차 : slow/fast 방법 사용

하나씩 순회하는 slow 포인터와 두 칸씩 순회하는 fast 포인터를 만들어, fast 포인터가 마지막에 있을 때 절반까지 순회한 slow 포인트의 위치를 반환하는 방법 사용

시간 복잡도 O(N) 공간 복잡도 O(1)

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var middle: ListNode? = head
        var end: ListNode? = head

        while (end?.next != nil) {
            middle = middle?.next
            end = end?.next?.next
        }

        return middle
    }
}