I ran into this exact problem while preparing for technical interviews, and what struck me was how much clearer my understanding of pointers and references became once I implemented it myself rather than just reading about linked lists conceptually. Concatenating two linked lists sounds trivial — and the core idea genuinely is simple — but implementing it correctly, handling edge cases, and understanding why it works the way it does taught me a lot about how Python represents linked data structures under the hood. Here’s the complete walkthrough.
What a Linked List of Characters Looks Like
Unlike Python’s built-in list or str, a linked list isn’t a native Python type — I build it myself from individual node objects, each holding a value and a reference to the next node.
class Node:
def __init__(self, char):
self.char = char
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, char):
new_node = Node(char)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next:
current = current.next
current.next = new_node
def __str__(self):
chars = []
current = self.head
while current:
chars.append(current.char)
current = current.next
return "".join(chars)
Let me build two lists to work with:
list1 = LinkedList()
for ch in "Hello":
list1.append(ch)
list2 = LinkedList()
for ch in "World":
list2.append(ch)
print(list1) # Hello
print(list2) # World
The Core Idea Behind Concatenation
Concatenating two linked lists means making the last node of the first list point to the first node of the second list, effectively stitching them into one continuous chain. Crucially, this doesn’t require copying any character data at all — I’m just changing a single reference (next pointer) at the join point.
def concatenate(list1, list2):
if list1.head is None:
list1.head = list2.head
return list1
current = list1.head
while current.next:
current = current.next
current.next = list2.head
return list1
result = concatenate(list1, list2)
print(result) # HelloWorld
This is the entire operation, and it’s O(n) where n is the length of the first list, since I have to walk to its end before attaching the second list’s head. No characters are copied, moved, or reallocated — I’m purely rewiring a pointer.
Why This Is Fundamentally Different From String Concatenation
If I concatenate two Python strings with +, Python creates an entirely new string object, copying every character from both operands into fresh memory, because strings are immutable.
s1 = "Hello"
s2 = "World"
combined = s1 + s2 # allocates a brand new string, copies all 10 characters
Linked list concatenation, by contrast, reuses the existing nodes of both lists entirely — it’s O(n) to find the end of the first list, but the actual “joining” step itself is O(1), a single pointer reassignment. This is one of the classic trade-offs between linked lists and arrays/strings: linked lists make certain structural modifications (like concatenation, or insertion in the middle) cheap in terms of not needing to copy data, at the cost of not supporting fast random access (getting the nth character requires walking n nodes, unlike a string’s O(1) indexing).
Handling Edge Cases
A robust implementation needs to consider several edge cases I initially overlooked:
def concatenate_safe(list1, list2):
# Edge case: first list is empty
if list1.head is None:
list1.head = list2.head
return list1
# Edge case: second list is empty — nothing to do, list1 stays as-is
if list2.head is None:
return list1
# Edge case: concatenating a list with itself (creates a cycle!)
if list1 is list2:
raise ValueError("Cannot safely concatenate a list with itself — this creates a cycle")
current = list1.head
while current.next:
current = current.next
current.next = list2.head
return list1
The self-concatenation case is subtle but important: if list1 and list2 refer to the exact same underlying list object, walking to “the end” and attaching “the head” creates a cycle — the list would loop back on itself infinitely, breaking anything that tries to traverse or print it. I explicitly guard against this because it’s the kind of bug that causes a script to hang forever rather than fail with a clear error.
Implementing Without a Wrapper Class (Raw Node Chains)
Sometimes I work with raw node chains directly, without a LinkedList wrapper class — this is common in interview-style problems where you’re given just the head node of each list.
class Node:
def __init__(self, char, next=None):
self.char = char
self.next = next
def build_list(s):
head = None
tail = None
for ch in s:
node = Node(ch)
if head is None:
head = node
tail = node
else:
tail.next = node
tail = node
return head
def concatenate_heads(head1, head2):
if head1 is None:
return head2
current = head1
while current.next:
current = current.next
current.next = head2
return head1
def print_list(head):
chars = []
current = head
while current:
chars.append(current.char)
current = current.next
print("".join(chars))
head1 = build_list("Hello")
head2 = build_list("World")
combined_head = concatenate_heads(head1, head2)
print_list(combined_head) # HelloWorld
This version is more “bare metal” and mirrors what you’d typically be asked to implement in a coding interview, where you’re often just given head references rather than a full class wrapping them.
Using a Tail Pointer to Avoid Re-Traversal
If I’m going to be concatenating repeatedly, walking to the end of the first list every single time is wasteful — O(n) per concatenation adds up. Maintaining an explicit tail reference lets me skip that traversal entirely.
class LinkedListWithTail:
def __init__(self):
self.head = None
self.tail = None
def append(self, char):
node = Node(char)
if self.head is None:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
def concatenate(self, other):
if self.head is None:
self.head = other.head
self.tail = other.tail
return self
if other.head is None:
return self
self.tail.next = other.head
self.tail = other.tail # crucial: update tail to the other list's tail
return self
def __str__(self):
chars = []
current = self.head
while current:
chars.append(current.char)
current = current.next
return "".join(chars)
l1 = LinkedListWithTail()
for ch in "Hello":
l1.append(ch)
l2 = LinkedListWithTail()
for ch in "World":
l2.append(ch)
l1.concatenate(l2)
print(l1) # HelloWorld
With a maintained tail pointer, concatenation becomes truly O(1) — no traversal needed at all, since I already know exactly where the first list ends. This is the version I’d genuinely reach for in real, performance-sensitive code, rather than the version that walks to the end each time.
Immutability Considerations: Should Concatenation Mutate or Return New?
There’s a design decision worth thinking through: should concatenate() mutate list1 in place (as shown above), or should it return a brand-new list, leaving both inputs untouched?
def concatenate_non_mutating(head1, head2):
if head1 is None:
return copy_list(head2)
new_head = copy_list(head1)
current = new_head
while current.next:
current = current.next
current.next = copy_list(head2)
return new_head
def copy_list(head):
if head is None:
return None
new_head = Node(head.char)
current_old = head.next
current_new = new_head
while current_old:
current_new.next = Node(current_old.char)
current_new = current_new.next
current_old = current_old.next
return new_head
This non-mutating version is O(n + m) instead of O(n) (or O(1) with a tail pointer), since it must actually copy every node of both input lists to avoid altering the originals. Whether this trade-off is worth it depends entirely on whether callers expect their original lists to remain unchanged after concatenation — a genuinely important API design decision, and one I always document explicitly in any linked list class I write, since silent mutation of caller-owned data is a classic source of confusing bugs.
Real-World Applications
- Interview preparation and algorithmic fundamentals, since linked list manipulation is one of the most common categories of technical interview questions.
- Implementing custom text buffers or rope-like data structures, where efficient concatenation of large text chunks matters (some text editors use similar linked structures internally for exactly this reason).
- Building blocks for more complex data structures, like implementing a queue, deque, or certain graph representations, all of which build on the same node-and-pointer fundamentals.
- Teaching and understanding memory/reference semantics, since linked lists make explicit what’s often hidden in higher-level data structures — you can literally see and manipulate the pointers connecting pieces of data.
Common Mistakes
Forgetting to handle empty list edge cases, causing AttributeError: 'NoneType' object has no attribute 'next' when trying to traverse a list whose head is None.
Accidentally creating a cycle by concatenating a list with itself, or by reusing node objects across multiple lists without realizing they now share structure.
Walking to the end of the first list unnecessarily on every concatenation when a maintained tail pointer would make the operation O(1) instead.
Not deciding explicitly whether concatenation should mutate or copy, leading to surprising behavior for callers who expected their original lists to remain untouched.
Confusing linked list concatenation performance characteristics with string concatenation. They’re fundamentally different operations with different complexity profiles — conflating them leads to incorrect assumptions about performance in either direction.
Debugging Tips
- Always print or visualize small test lists before and after concatenation to confirm behavior matches expectations, especially around edge cases like empty lists.
- Add a cycle-detection check (using Floyd’s tortoise-and-hare algorithm, for instance) when debugging mysterious infinite loops in traversal code — a common symptom of an accidentally created cycle.
- Test with single-node lists and empty lists explicitly; these boundary cases catch the majority of real bugs in linked list implementations.
Performance and Complexity Summary
| Approach | Time Complexity | Notes |
|---|---|---|
| Traverse to end, then attach | O(n) | n = length of first list |
| Maintained tail pointer | O(1) | No traversal needed |
| Non-mutating (copies both lists) | O(n + m) | Preserves original lists |
FAQs
Does concatenating linked lists copy any character data? Not in the mutating version — it’s purely a pointer reassignment. Only the non-mutating version copies data, and only because it needs to preserve the original lists.
What happens if I concatenate a list with itself? Without an explicit guard, this creates a cycle, since the “end” of the list and the “start” you’re attaching become the same list, causing traversal to loop forever.
Is a linked list better than a Python string for building up a “HelloWorld”-style result? For pure character concatenation, Python’s own strings (or a list of characters joined at the end) are typically far more practical and performant in real code. Linked lists are primarily valuable here as a learning exercise and for genuinely different use cases (like frequent structural insertion/deletion) where their specific trade-offs pay off.
Why maintain a tail pointer instead of just always traversing? Maintaining a tail turns concatenation from O(n) into O(1) — a meaningful difference if concatenation happens frequently or on very long lists.
Summary
Concatenating two linked lists of characters in Python comes down to a single core idea: point the last node of one list to the first node of the other, without copying any underlying data. The real engineering considerations are in the edge cases — empty lists, self-concatenation cycles — and in the design choice between mutating in place (fast, but changes the caller’s original list) versus copying (safer for callers, but strictly more expensive). Maintaining a tail pointer turns what would otherwise be an O(n) traversal into a genuinely O(1) operation, which is the version worth reaching for whenever concatenation happens often.
References
- Python official documentation: Classes
- Python official documentation: Data model — object identity and
is - Python official documentation:
collections.deque, the standard library’s own efficient doubly linked list implementation