programming tagged posts

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...

First of all let’s clear thing up:

Finding the longest path of a graph algorithm is NOT the inverse of Dijkstra’s algorithm of finding the shortest path. In fact finding the longest path of a graph in NP-Hard problem.

In our case, the graph is a tree-shaped graph, more like a triangle.

Problem