educative.io

Time complexity clarification

Courses
,
#1

Can someone from code guru correct and respond?

linkedList.add() appends at the end of the linked list. This means it will first need to reach the end of list and then append, which is O(N^2) for each row where lefttoRight is false. unless java implementation remember the end of the list?
Adding at the front is o(1) because linked list knows the root.

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Zigzag Traversal (medium) - Grokking the Coding Interview: Patterns for Coding Questions

#2

Hi @bee1

Inserting an element at the end of the linked list will take O(N), as N would be the number of elements in the list that will be traversed. And yes, adding an element at the front will take O(1).

Also, the time complexity can be reduced to O(1) if we keep an additional pointer to the tail of the linked list.