golang 단일 연결 리스트 반전

머리말

컴퓨터 과학에서 연결 목록은 포인터를 통해 서로 연결된 일련의 노드로 구성된 기본 데이터 구조입니다. 연결 목록은 삽입 및 삭제 작업을 쉽게 구현할 수 있지만 요소를 찾으려면 순회가 필요하기 때문에 액세스 작업의 성능이 상대적으로 낮습니다. 이 기사에서는 Golang을 사용하여 단일 연결 목록의 반전 알고리즘을 구현하는 방법을 소개합니다.

단일 연결 목록의 정의

Golang에서는 구조를 사용하여 단일 연결 목록을 정의할 수 있습니다. 노드의 값 val과 다음 노드의 위치를 ​​가리키는 포인터를 포함하는 단일 연결 목록의 노드를 나타내는 구조 노드를 정의합니다.

type Node struct {
    val  int
    next *Node
}

링크드 리스트의 헤드 노드를 가리키는 헤드 포인터를 정의하세요. 연결된 목록이 비어 있으면 head는 nil을 가리킵니다.

var head *Node = nil

단일 연결 리스트 초기화

Golang에서는 새로운 함수를 사용하여 노드의 메모리를 할당하고 노드의 포인터를 반환할 수 있습니다.

func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}

newNode를 사용하여 지속적으로 노드를 추가하면 달성할 수 있는 단일 연결 목록을 만듭니다. 연결된 목록 1, 2, 3을 예로 들면 코드는 다음과 같습니다.

node1 := newNode(1)
node2 := newNode(2)
node3 := newNode(3)
  
node1.next = node2
node2.next = node3
head = node1

단일 연결 목록의 반전

단일 연결 목록의 반전을 달성하는 방법에는 반복과 재귀라는 두 가지 방법이 있습니다.

방법 1: 반복

반복 방법의 핵심 아이디어는 연결 리스트를 순회하고 현재 노드의 포인터를 이전 노드로 향하게 하여 반전의 목적을 달성하는 것입니다.

구체적인 구현 프로세스는 다음과 같습니다.

• 세 개의 포인터 정의: prev, head, next
• 연결된 목록을 탐색하고 head의 다음 포인터를 prev를 가리킵니다.
• 이전 포인터를 head를 가리킵니다
• head를 가리킵니다. next
• 헤드가 빌 때까지 위 단계를 반복합니다

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

func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}

방법 2: 재귀

재귀 방법의 핵심 아이디어는 링크된 끝까지 반복하는 것입니다. 먼저 나열한 다음 순회된 노드를 역순으로 반환합니다.

구체적인 구현 과정은 다음과 같습니다.

• 연결된 목록의 끝까지 재귀합니다.
• 다음 노드를 두 번째 노드를 가리킵니다.
• 두 번째 노드의 다음을 비우도록 가리킵니다.
• 위 단계를 반복합니다. 원본 링크드 리스트가 반환될 때까지 헤드 노드

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

func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}

전체 코드는 다음과 같습니다.

package main
  
import (
    "fmt"
)
  
type Node struct {
    val  int
    next *Node
}
  
func newNode(val int) *Node {
    return &Node{
        val,
        nil,
    }
}
  
var head *Node
  
func reverseList1(head *Node) *Node {
    var prev *Node = nil
    var next *Node = nil
  
    for head != nil {
        next = head.next
        head.next = prev
        prev = head
        head = next
    }
  
    return prev
}
  
func reverseList2(head *Node) *Node {
    if head == nil || head.next == nil {
        return head
    }
  
    newHead := reverseList2(head.next)
    head.next.next = head
    head.next = nil
  
    return newHead
}
  
func main() {
    node1 := newNode(1)
    node2 := newNode(2)
    node3 := newNode(3)
  
    node1.next = node2
    node2.next = node3
  
    head = node1
  
    fmt.Println("原链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList1(head)
  
    fmt.Println("
迭代法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
  
    head = node1
    head = reverseList2(head)
  
    fmt.Println("
递归法倒转后的链表：")
    for head != nil {
        fmt.Printf("%d->", head.val)
        head = head.next
    }
}

실행 결과는 다음과 같습니다.

原链表：
1->2->3->
迭代法倒转后的链表：
3->2->1->
递归法倒转后的链表：
3->2->1->

결론

이 글에서는 방법을 소개합니다. Golang을 사용하여 단일 연결 목록의 반전을 구현하고 반복과 재귀라는 두 가지 구현 방법을 소개합니다. 이 글을 통해 모두가 이 두 가지 방법의 핵심 아이디어를 마스터하고 이를 실제 개발에 유연하게 적용할 수 있다고 믿습니다.

위 내용은 golang 단일 연결 리스트 반전의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!