Discover data structures and algorithms using Python. Gain insights into solving real-world problems and typical interview questions with detailed reviews, explanations, and hands-on coding exercises.

Data structures and algorithms are among the most fundamental concepts of Computer Science. Whether it’s real-world problems you’re trying to solve or the typical coding question asked in an interview, almost every problem requires you to demonstrate a deep understanding of data structures and algorithms. 

This course is a detailed review of some of the most common data structures and algorithms that you’ll see in interviews and your everyday work. With implementation details, thorough explanations, and hands-on coding exercises, you’ll quickly gain the confidence you need to solve any problem, no matter the situation.

Data Structures and Algorithms in Python

In this lesson, we investigate how to sum two singly linked lists. Check out the code below, after which, we will do a line by line analysis of it. 

# Implementation

def sum_two_lists(self, llist):
  p = self.head  
  q = llist.head

  sum_llist = LinkedList()

  carry = 0
  while p or q:
      if not p:
          i = 0
      else:
          i = p.data
      if not q:
          j = 0 
      else:
          j = q.data
      s = i + j + carry
      if s >= 10:
          carry = 1
          remainder = s % 10
          sum_llist.append(remainder)
      else:
          carry = 0
          sum_llist.append(s)
      if p:
          p = p.next
      if q:
          q = q.next
  return sum_llist


# Explanation 
First of all, we initialize `p` and `q` to point to the heads of each of the two linked lists (**lines 2-3**). On **line 5**, we declare `sum_llist` and initialize it to a linked list. The data values of `sum_llist` will represent the final sum at the end of this method. `carry` is initialized to `0` on **line 7** and it will help us in evaluating the sum. 

With the help of `p` and `q`, we set up a `while` loop which will run until both `p` and `q` equal `None`. On **lines 9-16**, we have handled the cases if either `p` or `q` equal `None`. If `p` or `q` equal `None`, we set `i` or `j` to `0` accordingly. In the other case where `p` and `q` are not equal to `None`, we use the data values of the node they are pointing to and store the data values in variables `i` and `j`. We are using `i` to represent the current digit picked from the first linked list and `j` to represent the current digit picked from the second one.

Once we get the values in `i` and `j`, we evaluate the sum on **line 17** by adding `i`, `j`, and `carry` and storing the sum in variable `s`. Note that `carry` will be `0` in the first iteration. After calculating the sum, we check if that sum is greater than or equal to `10` on **line 18**. If `s` is greater than or equal to `10`, we set `carry` to `1` (**line 19**) and calculate the `remainder` using the modulus operator on **line 20**. Now we append `remainder` to the final linked list (`sum_llist`) on **line 20**. On the other hand, if `s` is less than `10`, then there is no carry (`carry = 0`), and we append `s` to `sum_llist`. These steps are almost the same as we perform the arithmetic operation of addition. On **line 25-28**, we update `p` and `q` to their next nodes if they are not already `None`. 

`sum_llist` is returned from the end of the method and contains the sum of the two linked lists we had at the start. 

The `sum_two_lists` has been made part of the `LinkedList` class. You can run it and verify our solution!

This lesson contains the solution review for the challenge of summing two linked lists. 

Introduction

Stack

Singly Linked Lists

Circular Linked Lists

Doubly Linked Lists

Arrays

Binary Trees

Binary Search Trees

Binary Search

Recursion

String Processing

Solution Review: Sum Two Linked Lists

Implementation #

Explanation #