백엔드 개발 Golang golang에서 연결리스트를 역방향으로 바꾸는 방법

golang에서 연결리스트를 역방향으로 바꾸는 방법

Apr 23, 2023 am 10:22 AM

연결된 목록을 뒤집는 것은 일반적인 질문이며 프로그래밍 인터뷰에서 자주 언급됩니다. 이는 널리 사용되는 고전적인 알고리즘 문제이며 연결 목록의 순서를 빠르게 바꾸는 데 사용할 수 있습니다. 이 글에서는 golang 언어를 사용하여 역방향 연결 목록을 구현하는 알고리즘과 단계를 소개합니다.

  1. 단일 연결 목록 노드 정의

역방향 연결 목록 구현을 시작하기 전에 단일 연결 목록 노드를 정의해야 합니다. 노드에는 데이터 필드와 포인터 필드라는 두 가지 매우 중요한 부분이 포함됩니다. 데이터 필드는 노드의 값을 저장하는 데 사용되고 포인터 필드는 다음 노드를 가리키는 데 사용됩니다.

golang에서는 구조체 구조를 사용하여 단일 연결 목록 노드를 정의할 수 있습니다. 구조에는 현재 노드의 값을 나타내는 데 사용되는 Val과 다음 노드에 대한 포인터를 나타내는 데 사용되는 Next라는 두 가지 특성이 포함되어 있습니다.

type ListNode struct {

Val  int
Next *ListNode
로그인 후 복사

}

  1. Singly linked list inversion

이제 단일 연결 목록의 노드를 정의했으므로 다음 단계는 연결 목록을 반전시키는 알고리즘을 구현하는 것입니다. 연결된 목록을 뒤집는 핵심은 연결된 목록을 탐색하고 각 노드에 대한 포인터를 변경하는 것입니다.

연결된 목록의 각 노드를 처음부터 순회하고 "다음" 포인터를 차례로 변경하여 이전 노드를 가리킬 수 있습니다. 이런 식으로 연결된 목록을 뒤집을 수 있습니다.

연결된 목록을 뒤집는 알고리즘 단계는 다음과 같습니다.

(1) 각각 첫 번째 노드와 두 번째 노드를 가리키는 pre 및 cur라는 두 개의 포인터를 정의합니다. pre는 이전 노드이고 cur는 현재 노드입니다.

(2) 연결된 목록을 탐색하고 현재 노드의 Next 포인터가 이전 노드 pre를 가리킵니다.

(3) 포인터를 뒤로 이동하여 pre는 현재 노드를 가리키고 cur는 다음 노드를 가리킵니다.

(4) 전체 연결된 목록을 탐색할 때까지 2단계와 3단계를 반복합니다.

구현 코드는 다음과 같습니다.

func reverseLinkedList(head ListNode) ListNode {

var pre *ListNode
cur := head
for cur != nil {
    next := cur.Next
    cur.Next = pre
    pre = cur
    cur = next
}
return pre
로그인 후 복사

}

  1. 역방향 연결리스트 테스트 코드

역방향 연결리스트의 정확성을 검증하기 위해, 실행할 테스트 코드를 작성하세요.

func TestReverseLinkedList(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseLinkedList(head)

assert.Equal(t, newHead.Val, 5)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 1)
로그인 후 복사

}

  1. 연결된 목록의 일부 역전

연결된 목록 전체를 역전시키는 것 외에도 연결된 목록의 일부를 역전시킬 수도 있습니다. 예를 들어 연결된 목록의 노드 m에서 노드 n으로 부분을 반전합니다. 전체 연결 목록을 뒤집어 약간만 수정하면 됩니다.

먼저 m-1번째 노드로 이동할 수 있으며, pre 포인터는 이 노드를 가리키고 cur는 m번째 노드를 가리킵니다. 그런 다음 n번째 노드로 되돌릴 때까지 연결 리스트를 되돌리는 단계를 수행합니다.

구현 코드는 다음과 같습니다.

func reverseBetween(head ListNode, m int, n int) ListNode {

dummy := &ListNode{0, head}
pre := dummy

for i := 1; i < m; i++ {
    pre = pre.Next
}

cur := pre.Next
for i := m; i < n; i++ {
    next := cur.Next
    cur.Next = next.Next
    next.Next = pre.Next
    pre.Next = next
}

return dummy.Next
로그인 후 복사

}

  1. 부분 연결 리스트를 반전시키는 테스트 코드

검증을 위해 부분 연결 목록 반전의 정확성을 확인하기 위해 몇 가지 테스트 코드를 작성합니다.

func TestReverseBetween(t *testing.T) {

head := &ListNode{Val: 1}
node1 := &ListNode{Val: 2}
node2 := &ListNode{Val: 3}
node3 := &ListNode{Val: 4}
node4 := &ListNode{Val: 5}

head.Next = node1
node1.Next = node2
node2.Next = node3
node3.Next = node4

newHead := reverseBetween(head, 2, 4)

assert.Equal(t, newHead.Val, 1)
assert.Equal(t, newHead.Next.Val, 4)
assert.Equal(t, newHead.Next.Next.Val, 3)
assert.Equal(t, newHead.Next.Next.Next.Val, 2)
assert.Equal(t, newHead.Next.Next.Next.Next.Val, 5)
로그인 후 복사

}

  1. Summary

이 기사에서는 golang을 사용하여 전체 연결된 목록을 뒤집고 연결된 목록의 일부를 뒤집는 것을 포함하는 역방향 연결 목록 알고리즘을 구현합니다. 목록. 연결리스트 반전은 면접에서 흔히 나오는 질문이자 연결리스트와 관련된 문제를 해결하기 위한 기본 알고리즘이기도 하다. 연결리스트 알고리즘에 관심이 있다면 빠르고 느린 포인터, 순환 연결리스트, 노드 삭제 등 다른 연결리스트 관련 알고리즘을 깊이 공부하는 것이 좋습니다.

위 내용은 golang에서 연결리스트를 역방향으로 바꾸는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Golang의 목적 : 효율적이고 확장 가능한 시스템 구축 Golang의 목적 : 효율적이고 확장 가능한 시스템 구축 Apr 09, 2025 pm 05:17 PM

Go Language는 효율적이고 확장 가능한 시스템을 구축하는 데 잘 작동합니다. 장점은 다음과 같습니다. 1. 고성능 : 기계 코드로 컴파일, 빠른 달리기 속도; 2. 동시 프로그래밍 : 고어 라틴 및 채널을 통한 멀티 태스킹 단순화; 3. 단순성 : 간결한 구문, 학습 및 유지 보수 비용 절감; 4. 크로스 플랫폼 : 크로스 플랫폼 컴파일, 쉬운 배포를 지원합니다.

Golang 및 C : 동시성 대 원시 속도 Golang 및 C : 동시성 대 원시 속도 Apr 21, 2025 am 12:16 AM

Golang은 동시성에서 C보다 낫고 C는 원시 속도에서 Golang보다 낫습니다. 1) Golang은 Goroutine 및 Channel을 통해 효율적인 동시성을 달성하며, 이는 많은 동시 작업을 처리하는 데 적합합니다. 2) C 컴파일러 최적화 및 표준 라이브러리를 통해 하드웨어에 가까운 고성능을 제공하며 극도의 최적화가 필요한 애플리케이션에 적합합니다.

Golang vs. Python : 주요 차이점과 유사성 Golang vs. Python : 주요 차이점과 유사성 Apr 17, 2025 am 12:15 AM

Golang과 Python은 각각 고유 한 장점이 있습니다. Golang은 고성능 및 동시 프로그래밍에 적합하지만 Python은 데이터 과학 및 웹 개발에 적합합니다. Golang은 동시성 모델과 효율적인 성능으로 유명하며 Python은 간결한 구문 및 풍부한 라이브러리 생태계로 유명합니다.

Golang vs. Python : 성능 및 확장 성 Golang vs. Python : 성능 및 확장 성 Apr 19, 2025 am 12:18 AM

Golang은 성능과 확장 성 측면에서 Python보다 낫습니다. 1) Golang의 컴파일 유형 특성과 효율적인 동시성 모델은 높은 동시성 시나리오에서 잘 수행합니다. 2) 해석 된 언어로서 파이썬은 천천히 실행되지만 Cython과 같은 도구를 통해 성능을 최적화 할 수 있습니다.

공연 경주 : 골랑 대 c 공연 경주 : 골랑 대 c Apr 16, 2025 am 12:07 AM

Golang과 C는 각각 공연 경쟁에서 고유 한 장점을 가지고 있습니다. 1) Golang은 높은 동시성과 빠른 발전에 적합하며 2) C는 더 높은 성능과 세밀한 제어를 제공합니다. 선택은 프로젝트 요구 사항 및 팀 기술 스택을 기반으로해야합니다.

Golang의 영향 : 속도, 효율성 및 단순성 Golang의 영향 : 속도, 효율성 및 단순성 Apr 14, 2025 am 12:11 AM

goimpactsdevelopmentpositively throughlyspeed, 효율성 및 단순성.

C와 Golang : 성능이 중요 할 때 C와 Golang : 성능이 중요 할 때 Apr 13, 2025 am 12:11 AM

C는 하드웨어 리소스 및 고성능 최적화가 직접 제어되는 시나리오에 더 적합하지만 Golang은 빠른 개발 및 높은 동시성 처리가 필요한 시나리오에 더 적합합니다. 1.C의 장점은 게임 개발과 같은 고성능 요구에 적합한 하드웨어 특성 및 높은 최적화 기능에 가깝습니다. 2. Golang의 장점은 간결한 구문 및 자연 동시성 지원에 있으며, 이는 동시성 서비스 개발에 적합합니다.

Golang 및 C : 성능 상충 Golang 및 C : 성능 상충 Apr 17, 2025 am 12:18 AM

Golang과 C의 성능 차이는 주로 메모리 관리, 컴파일 최적화 및 런타임 효율에 반영됩니다. 1) Golang의 쓰레기 수집 메커니즘은 편리하지만 성능에 영향을 줄 수 있습니다. 2) C의 수동 메모리 관리 및 컴파일러 최적화는 재귀 컴퓨팅에서 더 효율적입니다.

See all articles