[LeetCode] 19. Remove Nth Node From End of List / Swift

[문제 보기]

Given the head of a linked list, remove the nth node from the end of the list and return its head.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

 

---

풀이 정리

 

1. 내가 짠 코드는 head를 가리키는 dummy 노드를 사용하지 않고 head 그대로를 사용하고 있지만, dummy 노드로  다루면 내가 짠 코드가 더 간단해질 수 있다(if n== stack.count쪽 부분에서 조건문이 없어짐)

2. 또 다른 풀이 방법은 front, rear포인터를 만들고 front만 먼저 n개만큼 먼저 이동한 후에 그 뒤로는 rear도 front와 함께 한칸씩 전진한다. front가 맨 마지막 노드까지 이동했을때 rear는 가장 마지막 노드의 위치 - 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 removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        
        var stack = [ListNode?]()
        var cur = head
        while cur != nil {
            stack.append(cur)
            cur = cur?.next
        }
        
        if n == stack.count {
            cur = head?.next
        } else {
            stack[stack.count - n - 1]?.next = stack[stack.count - n]?.next
            cur = head
        }
        
        return cur
    }
}