Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Linked Lists

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Sum List

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

List1 = 7, 1, 6. the number is 617
List2 = 5, 9, 2. the number is 295
The result of the sum is 912
The returned list should be: 2, 1, 9

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Of course, you could convert the linked lists to integers, compute the sum, and then convert it back to a new linked list. If you did this in an interview, your interviewer would likely accept the answer, and then see if you could do this without converting it to a number and back.

Try recursion. Suppose you have two lists, A = 1 - > 5 -> 9 (representing 951) and B 2 -> 3-> 6 ->7 (representing 7632), and a function that operates on the remainder of the lists (5 -> 9 and 3 -> 6 -> 7). Could you use this to create the sum method? What is the relationship between sum(1->5->9, 2->3->6->7) and sum(5->9, 3->6->7)?

Make sure you have considered linked lists that are not the same length.

Does your algorithm work on linked lists like 9->7->8 and 6->8->5? Double check that.

For the follow-up question: The issue is that when the linked lists aren't the same length, the head of one linked list might represent the 1000's place while the other represents the 1D's place. What if you made them the same length? Is there a way to modify the linked list to do that, without changing the value it represents?

👊 Solution 1

I wrote a straight forward solution, first I get all the values from each list into a string and then reverse them. Then you can sum the values of both strings, and put them in a new list - starting from the end of result string. The Runtime would be O(N + M).

public static SingleLinkedListNode sumList(SingleLinkedListNode list1, SingleLinkedListNode list2) {
    String list1Values = getListNumbersInReverse(list1);
    String list2Values = getListNumbersInReverse(list2);
    int sum = Integer.parseInt(list1Values) + Integer.parseInt(list2Values);

    String stringedResult = Integer.toString(sum);

    char c = stringedResult.charAt(stringedResult.length() - 1);
    int data = c - '0';

    SingleLinkedListNode result = new SingleLinkedListNode(data);

    for (int i = stringedResult.length() - 2; i >= 0; i--) {
        c = stringedResult.charAt(i);
        data = c - '0';
        result.appendToTail(data);
    }

    return result;
}

private static String getListNumbersInReverse(SingleLinkedListNode singleLinkedListNode) {
    StringBuilder listNumbers = new StringBuilder();
    SingleLinkedListNode n = singleLinkedListNode;

    while (n.next != null) {
        listNumbers.append(n.data);
        n = n.next;
    }
    listNumbers.append(n.data);
    listNumbers.reverse();
    return listNumbers.toString();
}

👊 Solution 2

xxxx

public boolean solution(String s1, String s2) {
    return false;
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/7/2020
← PartitionPalindrome →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
  • 👊 Solution 2
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr