이번 포스팅에서는 또 다른 연결리스트 알고리즘을 살펴보겠습니다. 이게 좀 더 어렵네요.
연결된 목록의 끝에서 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!