golang에서 연결리스트를 역방향으로 바꾸는 방법
- PHPz원래의
- 2023-04-23 10:22:20781검색
연결된 목록을 뒤집는 것은 일반적인 질문이며 프로그래밍 인터뷰에서 자주 언급됩니다. 이는 널리 사용되는 고전적인 알고리즘 문제이며 연결 목록의 순서를 빠르게 바꾸는 데 사용할 수 있습니다. 이 글에서는 golang 언어를 사용하여 역방향 연결 목록을 구현하는 알고리즘과 단계를 소개합니다.
- 단일 연결 목록 노드 정의
역방향 연결 목록 구현을 시작하기 전에 단일 연결 목록 노드를 정의해야 합니다. 노드에는 데이터 필드와 포인터 필드라는 두 가지 매우 중요한 부분이 포함됩니다. 데이터 필드는 노드의 값을 저장하는 데 사용되고 포인터 필드는 다음 노드를 가리키는 데 사용됩니다.
golang에서는 구조체 구조를 사용하여 단일 연결 목록 노드를 정의할 수 있습니다. 구조에는 현재 노드의 값을 나타내는 데 사용되는 Val과 다음 노드에 대한 포인터를 나타내는 데 사용되는 Next라는 두 가지 특성이 포함되어 있습니다.
type ListNode struct {
Val int Next *ListNode
}
- 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
}
- 역방향 연결리스트 테스트 코드
역방향 연결리스트의 정확성을 검증하기 위해, 실행할 테스트 코드를 작성하세요.
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)
}
- 연결된 목록의 일부 역전
연결된 목록 전체를 역전시키는 것 외에도 연결된 목록의 일부를 역전시킬 수도 있습니다. 예를 들어 연결된 목록의 노드 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
}
- 부분 연결 리스트를 반전시키는 테스트 코드
검증을 위해 부분 연결 목록 반전의 정확성을 확인하기 위해 몇 가지 테스트 코드를 작성합니다.
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)
}
- Summary
이 기사에서는 golang을 사용하여 전체 연결된 목록을 뒤집고 연결된 목록의 일부를 뒤집는 것을 포함하는 역방향 연결 목록 알고리즘을 구현합니다. 목록. 연결리스트 반전은 면접에서 흔히 나오는 질문이자 연결리스트와 관련된 문제를 해결하기 위한 기본 알고리즘이기도 하다. 연결리스트 알고리즘에 관심이 있다면 빠르고 느린 포인터, 순환 연결리스트, 노드 삭제 등 다른 연결리스트 관련 알고리즘을 깊이 공부하는 것이 좋습니다.
위 내용은 golang에서 연결리스트를 역방향으로 바꾸는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!