연결리스트 끝에서 N번째 제거

이번 포스팅에서는 또 다른 연결리스트 알고리즘을 살펴보겠습니다. 이게 좀 더 어렵네요.

연결된 목록의 끝에서 n번째 노드를 제거하는 함수를 만듭니다.

leetcode 문제로 인해 발생합니다. 리트코드 문제처럼 'n'은 1부터 시작하여 1부터 목록의 길이까지 갈 수 있습니다.

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] {
    if n == 0 {
        return nil
    }
    fast := ll.Head // this moves to the end
    slow := ll.Head // this should be one behind the nth from end

    for count := 0; count < n; count++ {
        if fast == nil { // list is too short
            return nil
        }
        fast = fast.Next
    }
    if fast == nil { // special case, removing head
        res := ll.Head
        ll.Head = ll.Head.Next
        return res
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    res := slow.Next
    slow.Next = slow.Next.Next
    return res
}

이것의 핵심은 듀얼 포인터를 사용하는 것입니다. 목록의 선두에 대한 빠른 포인터와 느린 포인터를 초기화하는 것부터 시작합니다.

다음으로 빠른 포인터를 n 노드 앞으로 이동합니다. 이러한 방식으로 느린 포인터는 이제 빠른 포인터 뒤에 'n'이 됩니다. 이제 빠른 속도가 끝날 때까지 잠금 단계에서 두 포인터를 모두 이동할 수 있습니다.

그런 다음 마지막 노드까지 n번째를 제거하고 반환할 수 있습니다.

더 좋은 방법이 있나요? 댓글로 알려주세요.

감사합니다!

이 게시물과 이 시리즈의 모든 게시물에 대한 코드는 여기에서 확인할 수 있습니다.

위 내용은 연결리스트 끝에서 N번째 제거의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!