LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 연결리스트의 시작 노드 head, 정수 n
2. output: 연결리스트의 뒤에서 n번째 노드를 제거 후 연결리스트 리턴
   • The number of nodes in the list is sz.
   • 1 <= sz <= 30
   • 0 <= Node.val <= 100
   • 1 <= n <= sz

Idea

뒤에서 n번째 노드를 찾는 것이기 때문에, 연결리스트를 앞에서 부터 순회하며 (현재 커서 - n)번째 노드를 갱신해주면 된다. → Sol1

메모리를 조금 더 사용하지만, 직관적인 방법으로 스택을 사용하여 연결리스트를 역순으로 쌓은 후 n번째 노드를 제거하는 방법도 가능하다. → Sol2

Solution

1. 커서로 타겟 노드 갱신

   n번째 이상 노드 부터 idx - n 노드를 target으로 갱신

   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
           var cursor = head
           val answer = ListNode(0)
           answer!!.next = head
           var removeCursor = answer
           var cnt = 1
           while (cursor != null) {
               if (cnt > n) removeCursor = removeCursor!!.next
               cnt++
               cursor = cursor!!.next
           }
           removeCursor!!.next = if (cnt >= n + 1) removeCursor!!.next!!.next else null
           return answer.next
       }
   }
   

   시간 복잡도: 연결리스트 순회 = n

   

2. Stack 사용

   Stack에 삽입 후 n번째 노드 제거

   import java.util.*
   
   /**
    * Example:
    * var li = ListNode(5)
    * var v = li.`val`
    * Definition for singly-linked list.
    * class ListNode(var `val`: Int) {
    *     var next: ListNode? = null
    * }
    */
   class Solution {
       fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
           val stack = LinkedList<ListNode>()
           stack.offerLast(ListNode(0)) // 리턴용 하나 삽입 -> 빈 연결리스트 리턴을 위해
           stack[0]!!.next = head
           var cursor = head
           while (cursor != null) {
               stack.offerLast(cursor)
               cursor = cursor!!.next
           }
           // n번째 노드 삭제 -> n-1과 n+1 연결
           stack[stack.size - n - 1]!!.next = stack[stack.size - n]!!.next
           return stack[0]!!.next
       }
   }
   

   시간 복잡도: 연결리스트 순회 = n

   

Point

1. 연결리스트의 노드 갯수가 최대 30이어서 그런가 메모리 사용의 큰 차이는 없음