The journey into software engineering is both exciting and challenging. For young developers just stepping into the world of coding, having a solid foundation is more important than mastering every new language or framework. The fundamentals you build early in your career will shape your problem-solving ability, code quality, and overall growth as an engineer.

Starting a career in software development can feel overwhelming – new languages to learn, tools to master, and expectations to meet. But just like building a house, a lasting career begins with a solid foundation. The early habits you build, the principles you embrace, and the mindset you cultivate will shape your trajectory for years to come. This EBook lays the groundwork for a strong, resilient, and fulfilling career in software engineering.

You can buy this book from here: https://antesh6.gumroad.com/l/ourkj

Buy book: Let’s talk about Coding Basics for young engineers https://antesh6.gumroad.com/l/ourkj

To find the longest common prefix among an array of strings, we can optimize the approach to reduce unnecessary comparisons and improve efficiency.

# Example usage:

strs = [“flower”, “flow”, “flight”]

Output: “fl”

To find the longest common prefix among an array of strings, we can use the following algorithm:

1. If the array is empty, return an empty string since there are no common prefixes.
2. Initialize the prefix as the first string in the array.
3. Iterate through the remaining strings in the array.
4. For each string, compare it character by character with the current prefix.
5. Update the prefix to be the common prefix found so far.
6. Continue until all strings have been compared.
7. Return the final prefix.

Here’s a Python implementation of the above algorithm:

def longest_common_prefix(strs):
    if not strs:
        return ""

    prefix = strs[0]

    for string in strs[1:]:
        i = 0
        while i < len(prefix) and i < len(string) and prefix[i] == string[i]:
            i += 1
        prefix = prefix[:i]
        if prefix == "":
            return ""

    return prefix

# Example usage:
strs = ["flower", "flow", "flight"]
print(longest_common_prefix(strs))  # Output: "fl"

This implementation iterates through each string in the array and compares it with the current prefix character by character. It updates the prefix to be the common prefix found so far. If at any point the prefix becomes empty (indicating no common prefix), the function returns an empty string. Otherwise, it returns the final prefix found.

Java Code

public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // Find the shortest string in the array
        String shortest = strs[0];
        for (String str : strs) {
            if (str.length() < shortest.length()) {
                shortest = str;
            }
        }

        // Initialize the prefix as the shortest string
        StringBuilder prefix = new StringBuilder(shortest);

        // Iterate through each string in the array
        for (String str : strs) {
            // Compare each character of the prefix with the current string
            for (int i = 0; i < prefix.length(); i++) {
                if (prefix.charAt(i) != str.charAt(i)) {
                    // If a character mismatch is found, update the prefix
                    prefix.delete(i, prefix.length());
                    break;
                }
            }
        }

        return prefix.toString();
    }

    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix(strs)); // Output: "fl"
    }
}

JavaScript Code

function longestCommonPrefix(strs) {
    if (strs.length === 0) {
        return "";
    }

    let prefix = strs[0];

    for (let i = 1; i < strs.length; i++) {
        let j = 0;
        while (j < prefix.length && j < strs[i].length && prefix[j] === strs[i][j]) {
            j++;
        }
        prefix = prefix.slice(0, j);
        if (prefix === "") {
            return "";
        }
    }

    return prefix;
}

// Example usage:
const strs = ["flower", "flow", "flight"];
console.log(longestCommonPrefix(strs));  // Output: "fl"

Now, let’s analyze the time complexity of this algorithm:

• Let n be the number of strings in the array, and let m be the average length of strings.
• The algorithm iterates through each string once, performing character comparisons until it reaches the end of either the prefix or the current string.
• In the worst case, each character in the prefix needs to be compared with each character in each string.
• Therefore, the time complexity is O(n * m), where n is the number of strings and m is the average length of strings in the array.

This algorithm is simple and effective, providing a straightforward solution to finding the longest common prefix among an array of strings.

Buy book – Let’s talk about Coding Basics for young engineers

Linked lists are fundamental data structures used to store and organize data. Merging two linked lists efficiently is a common task, especially when dealing with sorted data. In this guide, we’ll walk through a step-by-step approach to merging two linked lists in Java, complete with a practical example.

Step 1: Initialize Pointers

• Create a new linked list to store the merged result.
• Initialize pointers for the two input linked lists and the result linked list.

class ListNode {
    int val;
    ListNode next;
    
    public ListNode(int val) {
        this.val = val;
    }
}

public class MergeLinkedLists {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // Dummy node to simplify handling the head of the result list
        ListNode current = dummy;

        // Initialize pointers
        while (l1 != null && l2 != null) {
            // Compare elements
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }

            current = current.next;
        }

        // Handle remaining elements
        current.next = (l1 != null) ? l1 : l2;

        return dummy.next; // Skip the dummy node when returning the result
    }
}

Step 2: Traverse and Compare

• Traverse both input linked lists simultaneously.
• Compare the current elements pointed to by the two pointers.

In this example, we define a ListNode class to represent each node in the linked list. The mergeTwoLists method takes two sorted linked lists (l1 and l2) and merges them into a new sorted linked list.

Step 3: Merge Elements

• If the element in the first linked list is smaller (or equal), add it to the result linked list and move the pointer in the first list to the next element.
• If the element in the second linked list is smaller, add it to the result linked list and move the pointer in the second list to the next element.

The method traverses both input linked lists simultaneously, comparing elements at each step. The smaller (or equal) element is added to the result linked list, and the respective pointer is moved to the next element.

Step 4: Handle Remaining Elements

Continue this process until reaching the end of one of the linked lists. If one list is longer than the other, simply append the remaining elements to the result linked list.

Step 5: Result Linked List

The mergeTwoLists method returns the merged and sorted linked list.

Python Example

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def merge_linked_lists(l1, l2):
    dummy = ListNode()  # Dummy node to simplify handling the head of the result list
    current = dummy

    while l1 and l2:
        if l1.value <= l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next

        current = current.next

    # If one list is longer than the other, append remaining elements
    current.next = l1 or l2

    return dummy.next  # Skip the dummy node when returning the result

This approach assumes that the input linked lists are already sorted. If they are not, you may need to sort them first before merging.

Bonus Tips

The flexibility and simplicity of linked lists make them suitable for scenarios where dynamic data structures are required, and constant-time insertions and deletions are essential. Despite their overhead in terms of pointers, linked lists shine in situations where the benefits of dynamic memory allocation and ease of modification outweigh their drawbacks.

1. Dynamic Memory Allocation:

Linked lists allow dynamic memory allocation, as they can easily grow or shrink in size during program execution. This is particularly useful when the size of the data structure is unknown in advance.

2. Implementation of Other Data Structures:

Linked lists are used to implement more complex data structures like stacks and queues. For example, a linked list can be employed to create a dynamic stack where elements can be easily added or removed.

3. File Systems:

Linked lists are used in file systems to maintain the structure of directories. Each directory contains a linked list of entries, where each entry points to a file or a sub-directory.

4. Symbol Tables:

In compilers and interpreters, linked lists are often used to implement symbol tables, where variables and their associated information are stored.

5. Dynamic Hashing:

Linked lists are used in dynamic hashing to handle collisions. When two keys hash to the same location, a linked list at that location can store all the elements with the same hash value.

5. Memory Management in Operating Systems:

In operating systems, linked lists are used to manage memory. Free memory blocks are stored in a linked list, and when memory is allocated or deallocated, the linked list is updated accordingly.

7. Graph Representation:

Linked lists can be used to represent graphs. Each node in the linked list can represent a vertex, and the edges between vertices are represented by the links between nodes.

8. Undo Functionality in Software:

In applications with undo functionality, a linked list can be used to store a sequence of states. Each state change corresponds to a node in the linked list.

9. Music Player Playlist:

Playlists in music players can be implemented using linked lists. Each song can be represented as a node, and the links between nodes define the order of the playlist.

10. Polynomial Representation:

Linked lists are used to represent polynomials, especially in algebraic operations. Each node represents a term in the polynomial.

Feel free to incorporate this Java example into your projects or use it as a reference when working with linked lists and data merging tasks.

Joly coding!

Merging Two Linked Lists in Java: A Step-by-Step Guide with bonus tips at the end was originally published in Dev Genius on Medium, where people are continuing the conversation by highlighting and responding to this story.

Buy book: Let’s talk about Coding Basics for young engineers https://antesh6.gumroad.com/l/ourkj

Dynamic programming is a powerful technique for solving complex problems by breaking them down into simpler subproblems and solving each subproblem only once. The key insight behind dynamic programming is to solve each subproblem only once and store the solution, so that it can be reused whenever needed. This approach helps avoid redundant computations and dramatically improves the efficiency of the solution. It is particularly useful for optimization problems where the goal is to find the best solution among a set of possible solutions.

Key Principles of Dynamic Programming

1. Overlapping Subproblems: Dynamic programming is most effective when the problem exhibits overlapping subproblems, meaning that the same subproblems are encountered multiple times during the computation.
2. Optimal Substructure: The problem must have optimal substructure, which means that the optimal solution to the larger problem can be constructed from optimal solutions to its subproblems. This property allows us to build up the solution iteratively.
3. Memoization vs. Tabulation: Dynamic programming can be implemented using two main approaches: memoization and tabulation. Memoization involves storing the solutions to subproblems in a data structure (such as a dictionary or array), while tabulation involves solving subproblems in a bottom-up manner, starting with the smallest subproblems and gradually building up to the larger problem.

Applications of Dynamic Programming

Dynamic programming has a wide range of applications across various domains, including:

• Algorithm Design: Dynamic programming is commonly used to solve optimization problems, such as the knapsack problem, longest common subsequence, and shortest path problems.
• Sequence Alignment: In bioinformatics, dynamic programming is used to align sequences of DNA, RNA, or proteins to identify similarities and differences.
• Resource Allocation: Dynamic programming can be applied to optimize resource allocation in various scenarios, such as project scheduling, production planning, and inventory management.

Conclusion

Dynamic programming is a versatile and powerful technique that can greatly enhance problem-solving capabilities. By breaking down complex problems into simpler subproblems and efficiently solving them, dynamic programming offers elegant solutions to a wide range of challenges. Whether you’re a seasoned programmer or just getting started, understanding the principles of dynamic programming can open up new avenues for tackling complex problems and optimizing your code.

In future posts, we’ll delve deeper into specific dynamic programming problems and explore practical examples of how dynamic programming can be applied to solve real-world challenges. Stay tuned!

Buy book: Let’s talk about Coding Basics for young engineers https://antesh6.gumroad.com/l/ourkj

The Coin Change Problem is a classic optimization problem often solved using dynamic programming or greedy algorithms. Here, I’ll provide both a greedy algorithm and an optimized dynamic programming solution

Example: For target amount 36 and coin denominations [1, 5, 10, 25], the greedy algorithm would select 25, 10, and 1, totaling 36.

Greedy Algorithm

In the greedy algorithm for the coin change problem, we sort the coin denominations in descending order and then iteratively select the largest denomination coin that is less than or equal to the remaining amount. This process continues until the remaining amount becomes zero.

def coin_change_greedy(coins, amount):
    # Sort coins in descending order
    coins.sort(reverse=True)  
    
    num_coins = 0
    for coin in coins:
        if amount == 0:
            break
        num_coins += amount // coin
        amount %= coin
    
    if amount == 0:
        return num_coins  # If amount is zero, return the number of coins used
    else:
        return -1  # If change cannot be made, return -1

# Example usage:
coins = [1, 5, 10, 25]  # Coin denominations
amount = 36
print("Minimum number of coins (greedy):", coin_change_greedy(coins, amount))

This implementation sorts the coins in descending order and then iterates through the coins, selecting the largest denomination coins that can be used while decrementing the remaining amount. It returns the total number of coins used if change can be made, or -1 if change cannot be made. Note that this greedy algorithm may not always produce the optimal solution for arbitrary coin denominations.

Time Complexity Analysis

• Sorting the coins initially takes O(n log n) time, where n is the number of coin denominations.
• The main loop iterates over each coin denomination once, resulting in a linear time complexity of O(n).
• Overall, the time complexity of the greedy algorithm for the coin change problem is O(n log n) due to the sorting step.

It’s important to note that while the greedy algorithm has a time complexity of O(n log n) due to sorting, in many practical cases where the number of coin denominations is small and the denominations are known in advance, the sorting step can be considered negligible, resulting in a linear time complexity of O(n) for the algorithm. However, if the number of coin denominations is large and unknown, or if the denominations are dynamically changing, the sorting step may become significant.

Optimized Dynamic Programming Solution

The dynamic programming solution for the coin change problem involves building a table where each cell represents the minimum number of coins needed to make up the corresponding amount. We iteratively fill the table using the minimum of either including the current coin or excluding it.

1. Initialization

• We start by initializing a dynamic programming array dp, where dp[i] represents the minimum number of coins needed to make up the amount i.
• Initially, we set all values in dp to infinity, except for dp[0], which is set to 0 because no coins are needed to make up the amount 0.

2. Iterative Filling of DP Table

• We iterate over each coin denomination in the coins array.
• For each coin denomination coin, we iterate over all possible amounts from coin to amount.
• At each iteration, we update the value of dp[i] to be the minimum of its current value and dp[i - coin] + 1.
• This represents the optimal solution for the current amount i, considering whether or not to include the current coin denomination coin.

3. Final Result

• After filling the entire dp table, the value of dp[amount] represents the minimum number of coins needed to make up the given amount.
• If dp[amount] is still infinity, it means that it is not possible to make up the amount using the available coin denominations, so we return -1.

def coin_change_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: 0 coins needed for amount 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1  # If change cannot be made, return -1

# Example usage:
coins = [1, 5, 10, 25]  # Coin denominations
amount = 36
print("Minimum number of coins (DP):", coin_change_dp(coins, amount))

Time Complexity Analysis:

Let’s analyze the time complexity of the dynamic programming solution:

Initialization

Initializing the dp array takes constant time, O(1).

Filling DP Table:

• We have a nested loop structure:
• The outer loop iterates over each coin denomination, taking O(N) time, where N is the number of coin denominations.
• The inner loop iterates over all possible amounts from coin to amount, taking O(amount) time.
• Therefore, the total time complexity for filling the DP table is O(N * amount), where N is the number of coin denominations and amount is the given target amount.

Final Result

Determining the final result by accessing dp[amount] takes constant time, O(1).

Overall Time Complexity

The dominant factor in the time complexity is the filling of the DP table, which is O(N * amount), where N is the number of coin denominations and amount is the given target amount. The initialization and determining the final result both contribute constant time, so they do not significantly affect the overall time complexity.

In summary, the time complexity of the optimized dynamic programming solution for the coin change problem is O(N * amount), where N is the number of coin denominations and amount is the given target amount.

Both solutions provide the minimum number of coins needed to make up the given amount. The greedy algorithm may not always produce the optimal solution for arbitrary coin denominations, while the dynamic programming solution guarantees the optimal solution. However, the greedy algorithm is often faster and simpler.

Joly Coding!

Buy book: Let’s talk about Coding Basics for young engineers https://antesh6.gumroad.com/l/ourkj

A greedy algorithm is an approach to problem-solving that involves making locally optimal choices at each step with the hope of finding a globally optimal solution. At each step, the algorithm selects the best available option without considering the consequences of that choice on future steps. Greedy algorithms are typically used for optimization problems, where the goal is to find the best solution from a set of possible solutions.

Here are the basic steps involved in designing and implementing a greedy algorithm:

Define the Problem

Clearly define the problem you are trying to solve and the criteria for optimization.

Identify Greedy Choice Property

Determine the property that allows you to make greedy choices at each step. This property ensures that selecting the locally optimal solution leads to an optimal solution overall.

Design the Algorithm

Develop a strategy to iteratively make greedy choices and update the solution.

Implement the Algorithm

Write the algorithm using a programming language of your choice, ensuring that it follows the greedy strategy defined earlier.

Analyze the Solution

After obtaining the solution, analyze its correctness and optimality. Sometimes, you may need to prove that the greedy algorithm always produces the optimal solution for the given problem.

Optimization and Refinement

If necessary, refine the algorithm to improve its performance or to handle additional constraints.

Example problems where greedy algorithms are commonly applied include:

• Coin Change Problem: Given a set of coin denominations and a target amount, find the minimum number of coins needed to make up that amount.
• Fractional Knapsack Problem: Given a set of items with weights and values, and a knapsack with a maximum weight capacity, determine the maximum value of items to include in the knapsack without exceeding its capacity.
• Minimum Spanning Tree: Given a graph with weighted edges, find a spanning tree with the minimum total weight.
• Huffman Coding: Given a set of characters and their frequencies, find an optimal binary prefix code that minimizes the total encoded message length.

Time Complexity

The time complexity of a greedy algorithm is determined by the number of iterations required to find the solution. In many cases, greedy algorithms have linear or polynomial time complexity, making them efficient for solving large instances of problems. However, the time complexity can also be exponential or even worse in some cases, especially if the problem has a combinatorial nature.

Space Complexity

The space complexity of a greedy algorithm depends on the data structures used to represent the problem instance and the solution. Typically, greedy algorithms require only a constant amount of additional space beyond the input data, resulting in constant space complexity. However, this may vary depending on the problem and the specific implementation.

It’s important to note that while greedy algorithms are often simple and efficient, they may not always produce the optimal solution for every problem. In some cases, a greedy approach may lead to a suboptimal solution that is not globally optimal. Therefore, it’s essential to carefully analyze the problem and ensure that the greedy choice property holds to guarantee the correctness of the solution.

Overall, the time and space complexity of a greedy algorithm can vary depending on the problem and the specific implementation details. It’s important to analyze the complexity of each greedy algorithm on a case-by-case basis to understand its efficiency and performance characteristics.

Buy my book: Let’s talk about Coding Basics for young engineers https://antesh6.gumroad.com/l/ourkj

The window sliding technique using two pointers is an efficient approach to solving problems where you need to maintain a subarray or subsequence of a certain size while iterating through an array. The idea is to maintain a window of size k and slide it through the array while keeping track of the sum.

Window Sliding Technique using Two Pointers

1. Initialize Pointers: Start with two pointers, usually named left and right, and set them to the beginning of the array.
2. Maintain the Window: Move the right pointer to the right to expand the window while keeping the left pointer fixed. This is done until the desired window of size k is reached.
3. Update Information: While expanding the window, update the information you need (e.g., sum, product, frequency, etc.). In this case, calculate the sum of elements within the window. Update the maximum sum if the current sum is greater.
4. Shrink the Window: Once the window size is reached, move the left pointer to the right to shrink the window. Again, update the maximum sum if the current sum is greater. Move the window by incrementing both pointers.
5. Repeat: Continue steps 2–4 until the right pointer reaches the end of the array.

Approach

• Use two pointers, left and right, to maintain the window.
• Use a variable to keep track of the current sum within the window.
• Update the maximum sum whenever a new maximum is found.

Example — Maximum Sum Subarray of Size K

def max_sum_subarray(arr, k):
    if k > len(arr) or k <= 0:
        return "Invalid input: k is not valid"

    left = 0
    right = 0
    current_sum = 0
    max_sum = float('-inf')

    while right < len(arr):
        # Expand the window
        current_sum += arr[right]

        # Check if the window size is reached
        if right - left + 1 == k:
            max_sum = max(max_sum, current_sum)

            # Shrink the window
            current_sum -= arr[left]
            left += 1

        # Move the right pointer to the right
        right += 1

    return max_sum

# Example usage:
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 3
result = max_sum_subarray(arr, k)
print(f"Maximum sum subarray of size {k}: {result}")

In this example, the max_sum_subarray function uses the window sliding technique with two pointers to find the maximum sum subarray of size k. The left and right pointers are used to maintain the window, and the current_sum variable is updated accordingly. The maximum sum is updated whenever the window size is reached.

JavaScript

function maxSumSubarray(arr, k) {
  let left = 0;
  let right = 0;
  let currentSum = 0;
  let maxSum = 0;

  // Calculate sum for the first window
  for (let i = 0; i < k; i++) {
    currentSum += arr[i];
  }

  // Slide the window through the array
  while (right < arr.length) {
    // Update maxSum if currentSum is greater
    maxSum = Math.max(maxSum, currentSum);

    // Slide the window by moving left and right pointers
    currentSum = currentSum - arr[left] + arr[right];
    left++;
    right++;
  }

  return maxSum;
}

// Example usage:
const array = [4, 2, 1, 7, 8, 1, 2, 8, 1, 0];
const k = 3;
const result = maxSumSubarray(array, k);
console.log("Maximum Sum Subarray of size", k, "is:", result);

Java

public class MaxSumSubarray {

    public static int findMaxSumSubarray(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("Invalid input");
        }

        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;

        // Initialize the window
        for (int i = 0; i < k; i++) {
            currentSum += nums[i];
        }

        // Move the window
        for (int end = k; end < nums.length; end++) {
            currentSum += nums[end] - nums[end - k]; // Slide the window

            // Update the maximum sum
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 4, 2, 10, 2, 3, 1, 0, 20};
        int k = 4;

        int result = findMaxSumSubarray(nums, k);
        System.out.println("Maximum sum subarray of size " + k + ": " + result);
    }
}

Time Complexity

The time complexity of this algorithm is O(N), where N is the length of the input array. This is because we only iterate through the array once.

Note: This code assumes that the input array and the size of the subarray are valid. You may want to add additional input validation based on your specific requirements.

Window Sliding Technique — Find the maximum sum subarray of a fixed size k was originally published in Dev Genius on Medium, where people are continuing the conversation by highlighting and responding to this story.

Identifying if a linked list is a palindrome, is one of the classic examples of slow and fast pointers. To check if a linked list is a palindrome, you can follow these steps:

1. Find the middle of the linked list.

2. Reverse the second half of the linked list.

3. Compare the reversed second half with the first half.

Here’s the implementation along with the time complexity analysis

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Step 1: Find the middle of the linked list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the linked list
    prev, curr = None, slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Step 3: Compare the reversed second half with the first half
    first_half, second_half = head, prev
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next

    return True

# Example usage:
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(2)
node4 = ListNode(1)

node1.next = node2
node2.next = node3
node3.next = node4

print(isPalindrome(node1))  # Output: True

JavaScript

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function isPalindrome(head) {
  // Step 1: Find the middle of the linked list
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Step 2: Reverse the second half of the linked list
  let prev = null;
  let curr = slow;
  while (curr) {
    let nextNode = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextNode;
  }

  // Step 3: Compare the reversed second half with the first half
  let firstHalf = head;
  let secondHalf = prev;
  while (secondHalf) {
    if (firstHalf.val !== secondHalf.val) {
      return false;
    }
    firstHalf = firstHalf.next;
    secondHalf = secondHalf.next;
  }

  return true;
}

// Example usage:
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(2);
const node4 = new ListNode(1);

node1.next = node2;
node2.next = node3;
node3.next = node4;

console.log(isPalindrome(node1));  // Output: true

Java

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class PalindromeLinkedList {

    public boolean isPalindrome(ListNode head) {
        // Step 1: Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the linked list
        ListNode reversedSecondHalf = reverseList(slow);

        // Step 3: Compare the reversed second half with the first half
        ListNode firstHalf = head;
        while (reversedSecondHalf != null) {
            if (firstHalf.val != reversedSecondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            reversedSecondHalf = reversedSecondHalf.next;
        }

        return true;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

    public static void main(String[] args) {
        PalindromeLinkedList palindromeLinkedList = new PalindromeLinkedList();

        // Example usage:
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        System.out.println(palindromeLinkedList.isPalindrome(node1));  // Output: true
    }
}

Time Complexity

• Finding the middle of the linked list: O(n)

• Reversing the second half: O(n/2) => O(n)

• Comparing the two halves: O(n/2) => O(n)

The overall time complexity is O(n). The space complexity is O(1) since we are reversing the linked list in-place without using extra space proportional to the input size.

Algorithm, Time complexity to check if a linked list is a palindrome was originally published in Dev Genius on Medium, where people are continuing the conversation by highlighting and responding to this story.

Finding the middle of a linked list using two pointers is a common algorithmic problem. The approach involves using two pointers, one moving one step at a time (slow pointer) and the other moving two steps at a time (fast pointer). When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle.

Here’s an example implementation in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def findMiddle(head):
    if not head:
        return None

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

In this implementation, the findMiddle function takes the head of the linked list as input and returns the middle node. The termination condition for the while loop allows the fast pointer to reach the end, and the slow pointer lands exactly at the middle node for an odd-length linked list.

When the length of the linked list is odd, finding the middle involves advancing the slow pointer one extra step to land exactly at the middle node. The algorithm remains similar to the one for an even-length linked list but with a slight modification in the termination condition.

When the length of the linked list is even, the fast pointer reaches the end of the linked list, the slow pointer will be at the middle or the first middle node in the case of an even-length list.

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class LinkedListMiddle {
    public static ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        // Example usage for Odd length linked list:
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode middleNode = findMiddle(head);

        System.out.println(middleNode.val); // Output: 3
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class LinkedListMiddle {
    public static ListNode findMiddle(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        // Example usage for even length linked list:
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        ListNode middleNode = findMiddle(head);

        System.out.println(middleNode.val); // Output: 3, first middle
    }
}

The termination condition of the loop is when the fast pointer reaches the end or null. In the case of an even-length list, the slow pointer will be at the first middle node.

Time Complexity:

The time complexity of finding the middle of a linked list using two pointers is O(n), where n is the number of nodes in the linked list.

Bonus Point

The reason is that the fast pointer moves twice as fast as the slow pointer. In each iteration, the slow pointer advances by one node, and the fast pointer advances by two nodes. The fast pointer will reach the end of the list after approximately n/2 iterations, where n is the total number of nodes. The termination condition is when the fast pointer reaches the end of the linked list. Therefore, the time complexity is linear with respect to the number of nodes in the linked list.

Find the middle of a linked list using two pointers and it’s time complexity was originally published in Dev Genius on Medium, where people are continuing the conversation by highlighting and responding to this story.