Convert Singly Linked List to Doubly Linked List - codepath/compsci_guides GitHub Wiki

Unit 5 Session 2 (Click for link to problem statements)

TIP102 Unit 5 Session 2 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Linked Lists, Conversion, Pointers

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What happens if the singly linked list is empty?
    • The function should handle this gracefully and not perform any operations.
HAPPY CASE
Input: koopa_troopa = Node("Koopa Troopa") -> Node("Toadette") -> Node("Waluigi")
Output: koopa_troopa = Node("Koopa Troopa") <-> Node("Toadette") <-> Node("Waluigi")
Explanation: The singly linked list is converted into a doubly linked list by updating the `prev` pointers.

EDGE CASE
Input: koopa_troopa = None
Output: None
Explanation: When the linked list is empty, no changes are made.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List conversion problems, we want to consider the following approaches:

  • Updating pointers for prev and next attributes
  • Traversal of the linked list

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the singly linked list and update each node's prev pointer to point to the previous node.

1) Start at the head of the singly linked list.
2) Initialize a pointer `current` to the head and a pointer `prev_node` to `None`.
3) Traverse the list:
    a) Set the `prev` pointer of the current node to `prev_node`.
    b) Update `prev_node` to the current node.
    c) Move `current` to the next node.
4) Continue until the end of the list is reached.

⚠️ Common Mistakes

  • Forgetting to update the prev pointers for all nodes, leading to an incomplete doubly linked list.
  • Incorrectly handling the edge case where the list is empty.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None, prev=None):
        self.value = value
        self.next = next
        self.prev = prev

koopa_troopa = Node("Koopa Troopa")
toadette = Node("Toadette")
waluigi = Node("Waluigi")
koopa_troopa.next = toadette
toadette.next = waluigi

# Convert to doubly linked list
current = koopa_troopa
prev_node = None

while current:
    current.prev = prev_node
    prev_node = current
    current = current.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Verify the structure of the doubly linked list by printing it forwards and backwards.

Example:

print_linked_list(koopa_troopa)  # Expected Output: "Koopa Troopa -> Toadette -> Waluigi"
print_linked_list_backwards(waluigi)  # Expected Output: "Waluigi -> Toadette -> Koopa Troopa"

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(N) where N is the number of nodes in the linked list, as we need to traverse all nodes to update the prev pointers.
  • Space Complexity: O(1) because we are only using a constant amount of extra space for the pointers.