c tagged posts

Reverse Linked List in time O(n) & space O(1)

I’m not a dev but I do enjoy a coding challenge. In this blog post I will explain how to reverse a singly linked linked-list.

The data structure looks like this:

A simple code to implement a singly linked linkedlist is:

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}

To reverse the list: we need two pointers a previous pointer (prev) and a current one pointing to the current node we’re checking (curr). During exchanging pointers we will also a need a temporary pointer to hold the next pointer so we don’t lose track of our linked list during the reversing process

input: 1-2-3-4
output: 4-3-2-1

Needless to say you need to check for extreme cases such as an empty list, or a 1 element list.

Here is my code:

class Sol...
Read More