How to use PHP recursion to reverse a linked list

Linked list is a very common data structure, which is a collection of nodes. Each node contains a data item and a pointer to the next node. Linked lists can be used to implement data structures such as stacks, queues, and hash tables, and are often encountered in algorithm problems.

In many algorithmic problems, the linked list needs to be reversed. The basic idea of ​​reversing a linked list is to point each node in the linked list to its previous node, and finally make the first node the tail node of the linked list. This operation can be applied in various scenarios such as searching, merging, and sorting linked lists.

This article will introduce how to use PHP to implement the function of recursively reversing a linked list. If you don't know much about concepts such as linked lists and recursion, you can first learn the relevant basic knowledge on your own.

Implementation method

In the process of recursively reversing the linked list, the linked list needs to be split into two parts: the first node and the remaining part. After reversing the remaining parts, insert the first node at the end of the reversed list. This process can be implemented using recursion. The specific implementation is as follows:

/**
 * 反转链表
 * @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;
}

Code analysis

In the above code, we first process the base case, that is, when the node is empty or the next node is empty, directly Returns the node itself. Then, we recursively process the remaining nodes to obtain the reversed linked list.

Next, we insert the current node into the end of the reversed list. Specifically, we point the next node of the next node $head->next to the current node $head, empty the next node of $head, and finally return the reversed head node $newHead.

In addition, in order to better understand the above code, we also need to add a definition of linked list nodes:

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

Test case

In order to verify the above To ensure the correctness of the code, we can write the following test cases:

$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);

Executing the above test cases, we can get the following output results:

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

This article introduces how to use PHP recursion to implement the reversal operation of a linked list. Through the above demonstration, we can see the superiority of recursive algorithms in solving linked list problems. In actual development, we need to choose the most suitable algorithm to solve the problem based on the actual scenario. Hope this article is helpful to readers!

The above is the detailed content of How to use PHP recursion to reverse a linked list. For more information, please follow other related articles on the PHP Chinese website!