Skip to content

LeetCode

  • in LeetCode
  • 1 min read

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Bash
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

Explanation: 342 + 465 = 807.

Example 2:

Bash
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Solution Explanation

The approach for solving this problem will be, to traverse through each node of the linked list, carry out a sum on every step and return the final result. We just need to know the linked list data structure and the problem will be solved really easily.

solution.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nex
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

      dummy = ListNode()
      current = dummy
      carry = 0

      while (l1 or l2 or carry):
        n1 = l1.val if l1 else 0
        n2 = l2.val if l2 else 0
        s = n1 + n2 + carry

        current.next = ListNode(s%10)
        current = current.next
        carry = s//10

        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
      return dummy.next
  • in LeetCode
  • 1 min read

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1

Bash
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2

Bash
Input: list1 = [], list2 = [0]
Output: [0]

Solution Explanation

This problem just requires that you don't don't traverse through entire linked list when one of the linked list already has been traversed. It's already sorted so what we can do is, we can just traverse through until we reach the end of shorted list, then just join the remaining other list.

solution.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nex
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
      if not list1: return list2
      if not list2: return list1

      dummy = ListNode()
      current = dummy

      while list1 and list2:
        if list1.val < list2.val:
          current.next = list1
          list1 = list1.next
        else:
          current.next = list2
          list2 = list2.next
        current = current.next
      if list1:
        current.next = list1
      if list2:
        current.next = list2
      return dummy.next
  • in LeetCode
  • 1 min read

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution Explanation

The approach for solving this problem will be, to start from first number of the list, get a complement value by subtracting it from the target and check where that value belongs in the list.

We can use a hashmap for tracking indexes of the items so we won't have to iterate through the list over and over again as we look for complement value index.

solution.py
def twoSum(nums: List[int], target: int) -> List[int]:
  hashMap = {}
  n = len(nums)

  for i in range(n):
      complement = target - nums[i]
      if complement in hashMap:
          return [hashMap[complement], i]
      hashMap[nums[i]] = i
  return []

That's it for this problem, one of the easiest problem in LeetCode.