Reversing a Singly-Linked List in PHP: A Simple Approach

A singly-linked list consists of nodes, each containing a value and a reference (or pointer) to the next node in the sequence. In this post, we’ll explore a PHP solution that efficiently reverses a singly-linked list.

Introduction

Given the head of a singly linked list, reverse the list, and return the reversed list.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Reversing a singly-linked list involves changing the direction of pointers, effectively flipping the list.

Exploring the Code

Let’s delve into the PHP class Solution and its method reverseList($head):

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function reverseList($head) {
        $temp = null;
        while($head != null) {
            $temp2 = $head->next;
            $head->next = $temp;
            $temp = $head;
            $head = $temp2; 
        }     
        return $temp;
    }
}

How it Works

1. Initialization: The function initializes a variable $temp to hold the reversed list and sets it to null initially.
2. Reversal Logic:
   - Inside the while loop, it iterates through each node of the original list.
   - For each node, it stores the next node ($temp2) to avoid losing the reference.
   - It then updates the next pointer of the current node to point to the previously reversed list ($temp).
   - Updates the $temp to the current node for the next iteration.
   - Advances to the next node in the original list.
3. Return Value: Finally, it returns the reversed list ($temp), which now represents the original list in reverse order.

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the linked list.

Space Complexity: O(1) — Constant space is used throughout the process, regardless of the size of the input list.

Conclusion

The provided PHP solution efficiently reverses a singly-linked list using an iterative approach.

Happy Coding :)