이 질문은 새로운 개발자에게 가장 인기 있는 질문입니다. 괜찮은 데이터 구조 수업이 있다면 매우 간단합니다.

단일 연결 리스트를 뒤집습니다. (Leetcode 206입니다)

구현을 위해 연결 목록을 일반 유형으로 만들기로 선택했습니다.

type Node[T any] struct {
    Data T
    Next *Node[T]
}

type LinkedList[T any] struct {
    Head *Node[T]
}

func (ll *LinkedList[T]) Append(data T) {
    newNode := &Node[T]{Data: data, Next: nil}

    if ll.Head == nil {
        ll.Head = newNode
        return
    }

    current := ll.Head
    for current.Next != nil {
        current = current.Next
    }
    current.Next = newNode
}

역방향 기능의 경우 이전 노드에 대한 포인터를 유지한 다음 지정된 노드의 '다음'을 이전 노드로 설정하면 된다는 점을 인식하여 단일 패스로 완료됩니다.

끝에 도달하면 현재 노드가 목록의 새로운 '헤드'라는 것을 알 수 있습니다.

func (ll *LinkedList[T]) ReverseLinkedList() {
    var prev *Node[T] = nil
    var ptr *Node[T] = ll.Head
    for ptr != nil {
        var next *Node[T] = ptr.Next
        ptr.Next = prev
        prev = ptr
        if next == nil {
            ll.Head = ptr
        }
        ptr = next
    }
}

경계 조건을 놓쳤나요? 목록이 이제 이중 연결 목록이면 어떤 문제가 추가되나요? 댓글로 알려주세요.

감사해요!

이 게시물과 이 시리즈의 모든 게시물에 대한 코드는 여기에서 확인할 수 있습니다.