# LeetCode: Reverse Linked List Solution and Explanation

Hi,

If you’re interested in solving this problem then please try to spend at least one hour or more on it before looking at my solution.

Think about how you can use this table to write an iterative or recursive algorithm that reverses the linked list.

## The Solution

Bellow you’ll find my iterative and recursive solutions with explanations. The solutions are written in C#.

### The Recursive Solution

If you look at the table I made, you may notice that in order to reverse the list all you need to do is make the current node to point to the previous node during each recursive call, then move to the next node.

The stopping condition happens when the current node is null. Then you need to return the previous node, which points to the previous node, which points to the previous and so on. You’ve got a reversed linked list.

The complexity will be O(n) for time, because we need to cover the whole list and O(n) for space, because for every call made the program will allocate a new stack frame.

### The Iterative Solution

The iterative solution is similar with the recursive one, except it doesn’t allocate any extra space, it just iterates over the list, modifying it in place.

It updates the current node to the previous one and at the end it returns the last node.

The complexity is O(n) for time and O(1) for space.

```using System;

namespace LeetCode.November
{
{
public class ListNode
{
public int val;
public ListNode next;

public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}

// Space O(1) ; Time O(n)
{
ListNode prev = null;
{
// save next
// next -> prev
}

return prev;
}

// Space O(n) ; Time O(n)
public ListNode ReverseListRecursion(ListNode head, ListNode prev)
{
{
return prev;
}
}

{
return last;
}

public static void Test()
{
var r = problem.ReverseList(new ListNode(1, new ListNode(2, new ListNode(3))));
while (r != null)
{
Console.Write(\$"{r.val} ");
r = r.next;
}
}
}
}
```

# LeetCode: Flood Fill

Hello,

Here’s my solution for the flood fill problem, found on LeetCode.

If you want me to write about certain topics please let me know in the comments, thank you!

```"""
An image is represented by a 2-D array of integers, each integer representing the pixel
value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill,
and a pixel value newColor, "flood fill" the image.

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally
to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally
to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all
of the aforementioned pixels with the newColor.

At the end, return the modified image.
"""
from typing import List, Tuple

class Solution:
def __init__(self):
self.visited = set()

def _set_pixel(self, image: List[List[int]], point: Tuple[int, int], value: int):
try:
image[point][point] = value
except IndexError:
pass

def _get_pixel(self, image: List[List[int]], point: Tuple[int, int]):
if point < 0 or point < 0:
return None
try:
return image[point][point]
except IndexError:
return None

def _floodFill(self, image: List[List[int]], point: Tuple[int, int], color: int, newColor: int) -> List[List[int]]:
pixel = self._get_pixel(image, point)
if pixel is not None and pixel == color and point not in self.visited:
self._set_pixel(image, point, newColor)
self._floodFill(image, (point, point + 1), color, newColor)
self._floodFill(image, (point, point - 1), color, newColor)
self._floodFill(image, (point + 1, point), color, newColor)
self._floodFill(image, (point - 1, point), color, newColor)

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
point = (sr, sc)
pixel = self._get_pixel(image, point)
self.visited = set()
if pixel is not None:
self._floodFill(image, point, pixel, newColor)
return image

if __name__ == '__main__':
s = Solution()

out = s.floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)
print("Output", out)
assert out == [[2,2,2],[2,2,0],[2,0,1]]

out = s.floodFill([[0,0,0],[0,0,0]], 0, 0, 2)
print("Output", out)
assert out == [[2,2,2],[2,2,2]]

out = s.floodFill([[0,0,0],[0,1,1]], 1, 1, 1)
print("Output", out)
assert out == [[0, 0, 0], [0, 1, 1]]

```

# LeetCode: Find The Town Judge

Hello

In this article I will present you my Python3 solution for the following problem which I found on LeetCode: find-the-town-judge.

Note: The solution is on the second page, so you won’t get spoiled if you want to attempt to solve the problem by yourself. Have fun!

# LeetCode: Arrays 101: Inserting Items Into an Array

Hello,

Here are my solutions for the second part of the card: Arrays 101, from LeetCode.

## Duplicate Zeroes

Given an array of integers, remove duplicate zeroes and shift the remaining elements.

https://leetcode.com/problems/duplicate-zeros/

```class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
index = 0
arr_length = len(arr)
while index < arr_length:
if arr[index] == 0:
arr.insert(index, 0)
arr.pop()
index += 1
index += 1

```

## Merge Sorted Array

Given two sorted arrays, merge them together into nums1.

https://leetcode.com/problems/merge-sorted-array/

This problem wasn’t very Pythonic and I actually want to practice my problem solving skills together with my Python skills, so, I’ve took the liberty to modify the problem a little:

```from typing import List

class Solution:
def merge(self, nums1: List[int], nums2: List[int]) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
n = len(nums2)
# remove 0 from nums1
nums2_index = 0

for i, num in enumerate(nums1):
# We've reached the end of nums2, means we're merged.
if nums2_index == n:
break
if nums2[nums2_index] <= num:
nums1.insert(i, nums2[nums2_index])
nums2_index += 1

# If there's anything left in nums2 we'll add it to the end
for item in nums2[nums2_index:]:
nums1.append(item)

if __name__ == '__main__':
s = Solution()
a = [1,2,3]
s.merge(a, [2,5,6])
print(a)
```

Thank you!