[LinkedList] remove-nth-node-from-end-of-list - LeetCode Swift

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

Remove Nth Node From End of List - LeetCode

 

링크드리스트에 대한 개념이 없을 때 풀이방법

1. 링크드리스트를 배열로 변환
2. 배열에서 뒤에서 n번째 요소 삭제
3. 배열을 다시 링크드리스트로 변환

결과 : 속도는 기본적인 링크드리스트와 비슷했지만 메모리에서 엄청 낮은 점수를 받았다. 

 

코드

import Foundation

//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? {
        guard let head = head else { return ListNode(0)}
        var currentHead = head
        var arr = [Int]()
        var result = ListNode()
        
        if currentHead.next == nil {
            return nil
        }
        
        while currentHead.next != nil {
            arr.append(currentHead.val)
            currentHead = currentHead.next!
        }
     
        arr.append(currentHead.val)
        arr.remove(at: arr.count-n)
        result.val = arr[0]
        
        var nodeList = arr.map{ListNode($0)}
        for index in 1..<nodeList.count {
            nodeList[index-1].next = nodeList[index]
        }

        return nodeList[0]
    }
}

var sol = Solution()
print(sol.removeNthFromEnd(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2))
//print(sol.removeNthFromEnd(ListNode(1), 1))

 

---

 

링크드리스트 학습 후 풀이방법 (one pass로 하고싶었는데 아직은 무리니까 기초부터 해보자 쉽게!)

1. 전체를 1번 순회 후 총 count가 몇 개 인지 알아낸다. (1-2-3-4-5 면 5개)
2. count - n - 1 번째에서 next 노드에 next.next 노드를 붙인다.

 

코드

class Solution2 {
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var count = 1
        guard let head = head else {
            return nil
        }
        
        var currentNode = head
        while currentNode.next != nil {
            count += 1
            currentNode = currentNode.next!
        }
        
        guard count != 1 else {
            return nil
        }
        currentNode = head
        
        var nth = count - n
        guard nth != 0 else { return head.next}
        
        for num in 1..<nth {
            currentNode = currentNode.next!
        }
        currentNode.next = currentNode.next?.next
        
        return head
    }
}