[Algorithm] LeetCode - Reorder List

📠 문제

• Reorder List
• 난이도: Medium
• 주어진 리스트를 재배열하는 문제이다.

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.

💡 풀이

아래와 같은 조건이 있었기 때문에 기존의 리스트를 가지고 재배열을 해야했다.

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

아래처럼 연결리스트를 반으로 잘라 뒤집어서 번갈아 넣으면 되지 않을까? 생각했다.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

1 -> 2 -> 3 -> 4 | 5 <- 6 <- 7 <- 8

1️⃣ 배열 중간 찾기

아래와 같이 한칸, 두칸을 가는 노드를 만들어서 중간지점을 찾았다. O(n)

    var slow: ListNode? = head
    var fast: ListNode? = head

    while fast?.next != nil && fast?.next?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }

2️⃣ 중간부터 시작해서 배열 뒤집기

5 → 6 → 7 → 8 리스트를 5 ← 6 ← 7 ← 8 로 만든다.

    var postNode: ListNode? = nil
    var currentNode: ListNode? = slow?.next
    slow?.next = nil

    while let node = currentNode {
        let next = node.next
        node.next = postNode
        postNode = node
        currentNode = next
    }

3️⃣ 리스트 번갈아가면서 연결하기

1부터 시작, 8부터 시작해서 번갈아가면서 연결한다.

    var first: ListNode? = head
    var second: ListNode? = postNode

    while let node = second {
        let tmp1 = first?.next
        let tmp2 = node.next

        first?.next = second
        node.next = tmp1

        first = tmp1
        second = tmp2
    }

아래의 괜찮은 결과가 나왔다.

func reorderList(_ head: ListNode?) {
    guard let head = head, head.next != nil else { return }

    var slow: ListNode? = head
    var fast: ListNode? = head

    while fast?.next != nil && fast?.next?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }

    var postNode: ListNode? = nil
    var currentNode: ListNode? = slow?.next
    slow?.next = nil

    while let node = currentNode {
        let next = node.next
        node.next = postNode
        postNode = node
        currentNode = next
    }

    var first: ListNode? = head
    var second: ListNode? = postNode

    while let node = second {
        let tmp1 = first?.next
        let tmp2 = node.next

        first?.next = second
        node.next = tmp1

        first = tmp1
        second = tmp2
    }
}