Golang 언어를 사용하여 연결 목록 합계 알고리즘을 구현하는 방법

연결된 목록을 합산하는 것은 일반적인 알고리즘 문제입니다. 기본 아이디어는 두 개의 연결된 목록에 숫자를 추가하여 합계를 나타내는 새 연결 목록을 얻는 것입니다. 이 합계에는 캐리의 경우 숫자가 증가할 수 있습니다.

이 글에서는 golang 언어를 사용하여 연결 목록 합산 알고리즘을 구현하는 방법을 소개합니다.

먼저 두 개의 필드를 포함하는 연결된 목록 노드의 구조를 정의해야 합니다. val은 노드의 값을 나타내고 next는 다음 노드에 대한 포인터를 나타냅니다.

type ListNode struct {
    Val  int
    Next *ListNode
}

다음으로, 두 개의 연결 리스트 l1과 l2를 받고 그 합으로 구성된 새 연결 리스트를 반환하는 AddTwoNumbers 함수를 정의할 수 있습니다.

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0  // 进位值
    dummy := &ListNode{Val: 0, Next: nil}
    curr := dummy  // 当前节点

    for l1 != nil || l2 != nil {
        // 如果两个链表长度不相等，在较短的链表上添加一个0节点，使两个链表长度相等
        if l1 == nil {
            l1 = &ListNode{Val: 0, Next: nil}
        }
        if l2 == nil {
            l2 = &ListNode{Val: 0, Next: nil}
        }

        sum := l1.Val + l2.Val + carry
        carry = sum / 10  // 更新进位值
        curr.Next = &ListNode{Val: sum % 10, Next: nil}
        curr = curr.Next

        l1 = l1.Next
        l2 = l2.Next
    }

    // 最后如果还有进位，添加一个进位节点
    if carry > 0 {
        curr.Next = &ListNode{Val: carry, Next: nil}
    }

    return dummy.Next
}

이 함수에서는 캐리 변수를 사용하여 캐리 값을 표현하며 초기 값은 0입니다. 우리는 새 연결 리스트의 헤드를 가리키는 더미 노드 더미와 새 연결 리스트의 현재 노드를 가리키는 포인터 curr를 정의하며, 초기 값은 더미 노드를 가리킵니다. 그런 다음 for 루프를 사용하여 두 개의 연결 목록을 순회합니다. 이때 두 연결 목록의 길이가 동일하지 않으면 더 짧은 연결 목록에 0 노드를 추가하여 두 개를 만들어야 합니다. 연결된 목록의 길이가 동일합니다. 다음으로 연결 리스트의 동일한 위치에 노드를 추가하고 현재 노드의 값에 캐리 값을 추가하여 새로운 합계 값을 얻습니다. 이 합계 값의 10자리는 다음 추가에 전달될 수 있습니다. 따라서 캐리 값을 업데이트해야 합니다. 동시에 한 자리 숫자의 합계를 새 노드의 값으로 사용하고 새로 생성된 이 노드를 curr 포인터로 가리킵니다. 마지막으로 curr 포인터가 새 연결 목록의 다음 노드를 가리키도록 하고 l1 및 l2의 포인터를 다음 노드로 이동합니다. 연결된 목록이 모두 탐색될 때까지 이 과정을 반복합니다. 마지막으로 캐리가 있으면 캐리 노드를 추가합니다. 마지막으로 새 연결 목록의 헤드 노드를 나타내는 dummy.Next가 반환됩니다.

다음으로 AddTwoNumbers 함수를 테스트하는 테스트 함수를 정의할 수 있습니다.

func TestAddTwoNumbers(t *testing.T) {
    l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
    l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}
    l3 := AddTwoNumbers(l1, l2)
    if l3.Val != 7 || l3.Next.Val != 0 || l3.Next.Next.Val != 8 || l3.Next.Next.Next != nil {
        t.Errorf("AddTwoNumbers(%v, %v) = %v, want %v", l1, l2, l3, &ListNode{Val: 7, Next: &ListNode{Val: 0, Next: &ListNode{Val: 8, Next: nil}}})
    }
}

이 테스트 함수에서는 각각 342와 465를 나타내는 두 개의 연결된 목록 l1과 l2를 만듭니다. AddTwoNumbers 함수를 호출하고 그 합을 계산한 후 값이 708이어야 하는 새로운 연결 리스트 l3을 얻습니다. if 문을 사용하여 l3의 값을 확인합니다. 기대에 미치지 못하는 경우 t.Errorf 메서드를 사용하여 오류 메시지를 기록합니다.

위 코드를 sumLinkedList.go 파일에 저장하고 테스트 함수를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

$ go test -v
=== RUN   TestAddTwoNumbers
--- PASS: TestAddTwoNumbers (0.00s)
PASS
ok      sumLinkedList  0.360s

테스트 함수를 통해 연결된 목록 합산 알고리즘이 올바르게 구현되었음을 확인할 수 있습니다.

이 문서에서는 연결 목록 노드의 구조 정의와 AddTwoNumbers 함수를 구현하는 특정 단계를 포함하여 golang을 사용하여 연결 목록 합계 알고리즘을 구현하는 방법을 자세히 설명합니다. 이 알고리즘은 인터뷰에서 자주 접하는 질문입니다. 자체 구현을 통해 더 잘 준비할 수 있으며 연결 목록과 포인터에 대한 이해를 심화하는 데도 도움이 됩니다.

위 내용은 Golang 언어를 사용하여 연결 목록 합계 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!