PHP 재귀를 사용하여 연결 목록을 뒤집는 방법

연결된 목록은 노드의 모음인 매우 일반적인 데이터 구조입니다. 각 노드에는 데이터 항목과 다음 노드에 대한 포인터가 포함되어 있습니다. 연결 목록은 스택, 큐, 해시 테이블과 같은 데이터 구조를 구현하는 데 사용할 수 있으며 알고리즘 문제에서 자주 발생합니다.

많은 알고리즘 문제에서는 연결 목록을 반대로 바꿔야 합니다. 연결 리스트를 반전시키는 기본 아이디어는 연결 리스트의 각 노드를 이전 노드로 지정하고 마지막으로 첫 번째 노드를 연결 리스트의 꼬리 노드로 만드는 것입니다. 이 작업은 연결된 목록 검색, 병합, 정렬과 같은 다양한 시나리오에 적용될 수 있습니다.

이 기사에서는 PHP를 사용하여 연결 목록을 재귀적으로 역전하는 기능을 구현하는 방법을 소개합니다. 연결리스트, 재귀 등의 개념에 대해 잘 모르는 경우 먼저 관련 기본 지식을 스스로 배울 수 있습니다.

구현 방법

연결된 목록을 재귀적으로 역전하는 과정에서 연결 목록을 첫 번째 노드와 나머지 부분, 두 부분으로 나누어야 합니다. 나머지 부분을 반전시킨 후 반전된 목록의 끝에 첫 번째 노드를 삽입합니다. 이 프로세스는 재귀를 사용하여 구현할 수 있습니다. 구체적인 구현은 다음과 같습니다.

/**
 * 反转链表
 * @param ListNode $head 头节点
 * @return ListNode|null 反转后的头节点
 */
function reverseList($head) {
    // base case
    if ($head == null || $head->next == null) {
        return $head;
    }
    
    // 反转剩余部分
    $newHead = reverseList($head->next);
    
    // 将当前节点插入到反转后的链表末尾
    $head->next->next = $head;
    $head->next = null;
    
    return $newHead;
}

코드 분석

위 코드에서는 먼저 기본 사례를 처리합니다. 즉, 노드가 비어 있거나 다음 노드가 비어 있으면 노드 자체가 직접 반환됩니다. 그런 다음 나머지 노드를 재귀적으로 처리하여 역방향 연결 목록을 얻습니다.

다음으로 현재 노드를 역방향 목록의 끝에 삽입합니다. 구체적으로, 다음 노드 $head의 다음 노드를 현재 노드 $head 옆에 가리키고, $head의 다음 노드를 비우고, 마지막으로 반전된 헤드 노드 $newHead를 반환합니다.

또한 위 코드를 더 잘 이해하려면 연결 목록 노드의 정의도 추가해야 합니다.

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

테스트 사례

위 코드의 정확성을 확인하기 위해 다음과 같이 작성할 수 있습니다. 다음 테스트 케이스:

$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$newHead = reverseList($head);

print_r($newHead);

위의 테스트 케이스를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

ListNode Object
(
    [val] => 5
    [next] => ListNode Object
        (
            [val] => 4
            [next] => ListNode Object
                (
                    [val] => 3
                    [next] => ListNode Object
                        (
                            [val] => 2
                            [next] => ListNode Object
                                (
                                    [val] => 1
                                    [next] => 
                                )

                        )

                )

        )

)

Conclusion

이 기사에서는 PHP 재귀를 사용하여 연결 목록의 반전 작업을 구현하는 방법을 소개합니다. 위의 데모를 통해 연결리스트 문제를 해결하는 데 있어 재귀 알고리즘의 우수성을 확인할 수 있습니다. 실제 개발에서는 실제 시나리오를 기반으로 문제를 해결하는 데 가장 적합한 알고리즘을 선택해야 합니다. 이 글이 독자들에게 도움이 되기를 바랍니다!

위 내용은 PHP 재귀를 사용하여 연결 목록을 뒤집는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!