One Byte at a Time: Reverse a list

Difficulty Range: Sophomore

Reverse a list 

This is a little harder but I’ll explain the algorithm the best I can. This is a very important problem that you should try to solve.

This shouldn’t be a generic list make your own it’s very educational.

List, unlike arrays, are dynamic and friendly. This allows us to make things NULL and well just plain make things. 

Input  : 1 -> 2 -> 3  -> 4  -> 5  -> 6

Output: 6  -> 5  ->4  -> 3  ->2  -> 1

Make your own list system, don’t just use generic libraries.

Solution

//basic custom list

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
    //should work written on the fly sorry
    Public ListNode Add(ListNode head, int v) {
        if (head == null) {
            head.val = v;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new ListNode(v);
        }
    }
}
Code language: PHP (php)

So we need to use pointers. Wait, don’t run in fear. I mean easy pointers, the kind that don’t exist, they act as references and they might not technically be pointers. Really we just need to reference some pretend values to store things as we move the list. Because arrays are so different from lists this is not the same at all. Lists are lines of values while arrays are rigid orders of numbers all in different addresses. Instead of moving each value move what it is referencing to as the next object. This is not easy to understand so I recommend further study.

public static ListNode ReverseList(ListNode head)

{
    ListNode next; //pointer to the next
    ListNode prev = null; // point to the last one null at
    while (head != null) //till the end of the list
    {
        next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}
Code language: PHP (php)

Geeks for Geeks has a great GIF showing the algorithm at work.