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.

Reversing a Linked List: Easy as 1, 2, 3 | by Sergey Piterman | Outco | Medium

Subscribe to Blog via Email

Enter your email address to subscribe to Layers Media and receive notifications of new posts by email.

Join 80 other subscribers

David Kozdra

David Kozdra is a computer science student at Florida Polytechnic University. He is the Treasurer of the Media Club, Head of Outreach of the Baked Bean Bois improv group, and the Cohost of the Poly Pod podcast.

Leave a comment

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.