Add Two Numbers Represented as Linked List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does each node in the linked list represent in the 'Add Two Numbers Represented as Linked List' problem?

Each node represents a single digit of a number, stored in reverse order (ones place at the head).

beginner

Why do we add digits from the head of the linked lists in this problem?

Because the digits are stored in reverse order, the head contains the least significant digit, so addition starts from there.

beginner

What is the role of the carry in adding two numbers represented as linked lists?

Carry holds the overflow digit when sum of two digits exceeds 9, and it is added to the next digit sum.

intermediate

How do you handle linked lists of different lengths when adding two numbers?

Continue adding digits; if one list ends, treat missing digits as 0 until both lists and carry are processed.

intermediate

What is the time complexity of adding two numbers represented as linked lists?

O(max(m, n)) where m and n are the lengths of the two linked lists, since each node is processed once.

In the 'Add Two Numbers Represented as Linked List' problem, what does the head node represent?

A The most significant digit

B The least significant digit

C The carry value

D The sum of all digits

The head node stores the least significant digit because the number is stored in reverse order.

What should you do if one linked list is longer than the other during addition?

A Stop adding when the shorter list ends

B Ignore the longer list's extra digits

C Reverse both lists first

D Treat missing digits as zero and continue adding

You treat missing digits as zero to continue adding all digits and carry.

What happens if the final carry after adding all digits is not zero?

A It causes an error

B It is discarded

C It is added as a new node at the end

D It is subtracted from the last digit

The final carry is added as a new node to represent the extra digit.

What data structure is used to represent the numbers in this problem?

A Linked List

B Stack

C Array

D Queue

The problem uses linked lists to represent numbers digit by digit.

What is the main advantage of storing digits in reverse order in the linked list?

A Easier to add from least significant digit

B Saves memory

C Simplifies multiplication

D Allows sorting

Storing digits in reverse order allows addition starting from the least significant digit, simplifying the process.

Explain step-by-step how to add two numbers represented as linked lists.

Think about how you add numbers on paper from right to left.

Describe how to handle carry when adding two digits in linked lists.

Carry is like the extra you keep for the next digit.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" mean?
Each node contains a single digit and digits are stored in reverse order. What is the goal?

easy

A. Reverse both linked lists and then add the digits.

B. Multiply the two numbers and return the product as a linked list.

C. Add the two numbers digit by digit and return the sum as a linked list in reverse order.

D. Sort the linked lists before adding.

Solution

1. Step 1: Understand the representation of numbers in linked lists

   Each linked list node holds one digit, and the digits are stored in reverse order, meaning the first node is the ones place.

2. Step 2: Define the goal of the problem

   The goal is to add these two numbers digit by digit, handling any carry, and return the result as a new linked list in the same reverse order format.

3. Final Answer:

   Add the two numbers digit by digit and return the sum as a linked list in reverse order. -> Option C

4. Quick Check:

   Adding reversed digit lists = sum list reversed [OK]

Hint: Add digits node-wise with carry, keep result reversed [OK]

Common Mistakes:

• Trying to add numbers as integers directly
• Ignoring carry between digits
• Not returning the result in reverse order

2. Which of the following is the correct way to declare a node structure for a singly linked list in C for this problem?

easy

A. struct Node { int val; struct Node* prev; };

B. struct Node { int val; Node* next; };

C. struct Node { int val; struct Node next; };

D. struct Node { int val; struct Node* next; };

Solution

1. Step 1: Understand C struct syntax for linked list nodes

   In C, to define a node with an integer value and pointer to next node, use 'struct Node* next;'.

2. Step 2: Identify correct pointer usage

   struct Node { int val; struct Node* next; }; correctly uses 'struct Node* next;' which is the pointer to the next node. struct Node { int val; Node* next; }; misses 'struct' keyword, C uses struct Node instead of pointer, D uses 'prev' which is for doubly linked list.

3. Final Answer:

   struct Node { int val; struct Node* next; }; -> Option D

4. Quick Check:

   Pointer to next node = struct Node* next [OK]

Hint: Use 'struct Node* next;' for next pointer in C struct [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node*
• Using struct Node instead of pointer for next
• Confusing singly linked list with doubly linked list

3. What is the output linked list after adding the two numbers represented by these linked lists?
List1: 2 -> 4 -> 3 -> null (represents 342)
List2: 5 -> 6 -> 4 -> null (represents 465)
Code snippet adds digits with carry:

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 7 -> 0 -> 7 -> null

Solution

1. Step 1: Add digits node by node with carry

   2+5=7 (carry 0), 4+6=10 (carry 1), 3+4+1=8 (carry 0)

2. Step 2: Form the resulting linked list

   Digits are 7 (ones), 0 (tens), 8 (hundreds), so linked list is 7 -> 0 -> 8 -> null.

3. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

4. Quick Check:

   342 + 465 = 807 reversed = 7->0->8 [OK]

Hint: Add digits with carry, store remainder, move forward [OK]

Common Mistakes:

• Not handling carry correctly
• Adding digits without carry from previous sum
• Confusing order of digits in output

4. Given this buggy code snippet for adding two linked lists, what is the main error?

while(l1 != NULL || l2 != NULL) {
  int sum = carry;
  if(l1 != NULL) { sum += l1->val; l1 = l1->next; }
  if(l2 != NULL) { sum += l2->val; l2 = l2->next; }
  carry = sum / 10;
  sum = sum % 10;
  newNode->val = sum;
  newNode = newNode->next;
}

medium

A. newNode->next is not initialized before assignment, causing undefined behavior.

B. Carry is not updated correctly after sum calculation.

C. Loop condition should be && instead of ||.

D. Sum should be reset to zero inside the loop.

Solution

1. Step 1: Analyze pointer usage for newNode

   The code assigns newNode->val but then moves newNode to newNode->next without initializing newNode->next, so newNode->next is likely NULL or garbage.

2. Step 2: Identify missing node creation

   Before moving newNode = newNode->next, a new node must be created and linked to newNode->next to avoid undefined behavior.

3. Final Answer:

   newNode->next is not initialized before assignment, causing undefined behavior. -> Option A

4. Quick Check:

   Always create new node before moving pointer [OK]

Hint: Always allocate new node before moving next pointer [OK]

Common Mistakes:

• Not creating new nodes for the result list
• Incorrect loop condition causing missed nodes
• Incorrect carry update logic

5. You have two linked lists representing numbers in reverse order:
List1: 9 -> 9 -> 9 -> 9 -> null (represents 9999)
List2: 1 -> null (represents 1)
What is the correct resulting linked list after adding these two numbers?

hard

A. 9 -> 9 -> 9 -> 9 -> 1 -> null

B. 0 -> 0 -> 0 -> 0 -> 1 -> null

C. 1 -> 0 -> 0 -> 0 -> 0 -> null

D. 0 -> 0 -> 0 -> 0 -> null

Solution

1. Step 1: Add digits with carry step-by-step

   9+1=10 (digit 0, carry 1), next 9+0+1=10 (digit 0, carry 1), repeat for next two 9s similarly.

2. Step 2: Handle final carry

   After last digit, carry is 1, so add new node with value 1 at the end.

3. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option B

4. Quick Check:

   9999 + 1 = 10000 reversed = 0->0->0->0->1 [OK]

Hint: Add carry after last nodes if non-zero [OK]

Common Mistakes:

• Forgetting to add final carry node
• Stopping addition early when one list ends
• Misplacing the carry digit in the result