[LeetCode] 206. Reverse Linked List / Swift

[문제 보기]

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

 

https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

 

---

단방향 연결리스트의 방향을 뒤집는 문제이다.

재귀, 비재귀 버전으로 각각 풀어야 했다.

 

재귀버전

/**
 * 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 reverseList(_ head: ListNode?) -> ListNode? {
        if head?.next == nil {
            return head
        }
        
        let p = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        
        return p
    }
}

 

반복문 버전

 

/**
 * 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 reverseList(_ head: ListNode?) -> ListNode? {
        var stack = [ListNode]()
        var cur = head
        while cur != nil {
            stack.append(cur!)
            cur = cur!.next
        }
        let start = ListNode(0)
        cur = start
        while !stack.isEmpty {
            let top = stack.removeLast()
            top.next = nil
            cur!.next = top
            cur = top
        }
        
        return start.next
    }
}