역방향 부분 연결리스트 golang

연결된 목록을 뒤집는 것은 고전적인 문제이고, 널리 사용되며, 시간 복잡도가 높지 않고, 구현하기 어렵지 않습니다. 이 기사에서는 golang에서 부분 연결 목록을 뒤집는 알고리즘을 구현하는 방법을 소개합니다.

연결 리스트 역전시키기

먼저 연결 리스트를 역전시키는 방법을 살펴보겠습니다. 반복 또는 재귀라는 두 가지 방법으로 구현할 수 있습니다.

1. 반복 방법

pre, cur, next 세 개의 포인터를 사용하여 반전 작업을 반복적으로 수행합니다. Pre와 next는 반전 후 재연결을 용이하게 하기 위해 cur의 이전 노드와 후속 노드를 저장하는 것입니다. 코드는 다음과 같습니다.

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

2. 재귀적 방법

재귀적 방법은 반복적 방법만큼 이해하기 쉽지는 않지만 실제로 재귀적 사고를 연습하는 좋은 예입니다. 재귀 연산에서 주목해야 할 점은 연결 리스트의 끝까지 재귀한 후 tail 노드를 헤드의 next 노드에 할당한 후 tail 노드를 새로운 헤드로 반환한다는 점이다. 코드는 다음과 같습니다.

func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

부분 연결 리스트 역전

연결 리스트 역전을 기본으로 부분 연결 리스트 역전 방법을 살펴보겠습니다. 문제의 설명은 다음과 같습니다.

연결된 목록과 두 개의 정수 m과 n이 주어지면 연결 목록을 m 위치에서 n 위치로 바꿉니다. 알고리즘 구현을 제공해야 합니다.

질문을 관찰하면 고려할 수 있도록 세 부분으로 나눌 수 있습니다.

1. 이전: 연결된 목록을 뒤집을 필요가 없습니다.
2. m과 n 사이: 연결 목록을 뒤집을 필요가 있습니다.
3. n이후: 그럴 필요가 없습니다. reverse Transfer linked list

따라서 pre 및 tail 변수를 사용하여 첫 번째 부분의 꼬리 노드와 두 번째 부분의 헤드 노드를 기록한 다음 두 번째 부분을 반전시켜야 합니다. 첫 번째 부분과 두 번째 부분의 헤드 노드는 두 부분의 헤드 노드를 연결하면 됩니다.

코드는 다음과 같습니다:

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m <= 0 || n < m {
        return head
    }
    
    // 特判，如果m=1，则不需要第一部分
    if m == 1 {
        return reverseN(head, n)
    }
    
    //  遍历到m-1位置，记录pre和tail
    var pre *ListNode = nil
    cur := head
    for i := 1; i < m; i++ {
        pre = cur
        cur = cur.Next
    }

    tail := cur // tail 记录第一部分的末尾是 cur             
    // 将第二部分进行反转操作
    new_head := reverseN(cur, n - m + 1)

    // 将第一部分与第二部分重新连接
    tail.Next = new_head
    if pre != nil {
        pre.Next = tail
        return head
    } else {
        return tail
    }
}

// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }
    if n == 1 {
        return head
    }
    var pre *ListNode = nil
    cur := head
    for i := 1; i <= n && cur != nil; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    head.Next = cur
    return pre
}

요약

연결 목록 역전은 연결 목록 인터뷰 질문에서 자주 나오는 질문입니다. 이 알고리즘 아이디어를 익히면 연결 목록 역전 문제를 해결할 수 있을 뿐만 아니라 다른 연결 목록 변환으로도 확장할 수 있습니다. 운영. 인터뷰를 진행할 때 역연결리스트는 다른 질문의 예시로 활용될 수 있는데, 이는 아이디어를 발전시키는 데 매우 중요합니다. golang에서 역방향 연결 목록과 부분 연결 목록 알고리즘을 구현하려면 포인터 사용, Nil 판단 및 기타 문제에 주의해야 합니다. 코드를 마스터한 후에는 구현이 매우 간단합니다.

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