I currently have a method that would append one linked list (list2) to the end of another (list1). It does this through a while loop, with each iteration appending the next node from list1 to list2's end, and so on.
My understanding is that this would be O(n) time complexity, as the number of iterations in the while loop is directly determined by the size of list2. If list2 has 15 nodes, the function performs 15 appends, if list2 has 1000 nodes, it performs 1000 appends.
Frequently, however, I keep seeing people note that this union can be performed in O(1) time complexity if you keep a pointer to the tail of list1. How is this possible? From my (admittedly limited) understanding, I can somewhat understand that individual appends are O(1), but if you are appending an entire list, doesn't it need to be in the while loop and scanning through all of list2 regardless, hence O(n)?
The key here is that you don't need to append the entire list. list2 is already a linked list, with each element linked to the following element, so if your list holds a reference to the first and last elements, all you really need to do is link them together. In pseudocode:
list1.tail.next = list2.head
union.head = list1.head
union.tail = list2.tail