The Problem
We are provided with a Node
class in the editor. Each Node
object has an integer data field, data
, and a Node
instance pointer, next
, which points to the next node in a linked list. A function insert
is also declared, which takes two parameters: a pointer, head
, pointing to the first node of a linked list, and an integer, data
, that must be added to the end of the list as a new Node
object.
Task
The task is to complete the insert
function so that it creates a new Node
(passing data
as the Node
constructor argument) and inserts it at the tail of the linked list referenced by the head
parameter. After the new node is added, the function should return the reference to the head
node.
Note: The
head
argument isnull
for an empty list.
The Input
The first line contains T
, the number of elements to insert. Each of the next T
lines contains an integer to insert at the end of the list.
Sample Input:
4
2
3
4
1
The Output
The function should return a reference to the head
node of the linked list.
Sample Output:
2 3 4 1
Explanation
T=4
, so your function will insert 4 nodes into an initially empty list. It will first return a new node that contains the data value 2 as the head of the list. Then it will create and insert nodes 3, 4, and 1 at the tail of the list.
The Solution
Here are three Python solutions, each with its own strengths and weaknesses:
Source Code 1
This solution creates a new node and then traverses the linked list to find the tail node, upon which it appends the new node. This solution is straightforward and intuitive but may be a bit slow for very large lists because it traverses the entire list to find the tail node.
class Node:
def __init__(self,data):
self.data = data
self.next = None
class Solution:
def display(self,head):
current = head
while current:
print(current.data,end=' ')
current = current.next
def insert(self,head,data):
node = Node(data)
if head:
tail = head
while tail.next:
tail = tail.next
tail.next = node
return head
return node
mylist= Solution()
T=int(input())
head=None
for i in range(T):
data=int(input())
head=mylist.insert(head,data)
mylist.display(head);
Source Code 2
This refactored solution does the same thing but has a slight improvement in readability. The logic of checking for an empty list is moved to the top of the insert function, making it immediately clear what happens in that case. This doesn't change the performance but enhances the readability and maintainability of the code.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def display(self, head):
current = head
while current:
print(current.data, end=' ')
current = current.next
def insert(self, head, data):
node = Node(data)
if not head:
return node
tail = head
while tail.next:
tail = tail.next
tail.next = node
return head
mylist = Solution()
T = int(input())
head = None
for _ in range(T):
data = int(input())
head = mylist.insert(head, data)
mylist.display(head)
Source Code 3
If we want to optimize the insert
function, we could maintain a reference to the tail of the list. However, since the scope of the optimization is limited to the insert
function, we cannot store the tail as an attribute of the Solution
class.
Here is an optimized version of the insert
function that uses a local static variable to keep track of the tail of the list. A local static variable is a variable that retains its value between the function calls.
Please note that this concept is not directly available in Python. However, we can achieve similar functionality using mutable objects like a list or a dictionary. In the following example, we use a list to simulate a static variable:
class Node:
def __init__(self,data):
self.data = data
self.next = None
class Solution:
def display(self,head):
current = head
while current:
print(current.data,end=' ')
current = current.next
def insert(self,head,data):
node = Node(data)
if not head:
self.tail = [node] # initialize the static variable
return node
else:
self.tail[0].next = node # update the next attribute of the tail node
self.tail[0] = node # update the tail node
return head
mylist = Solution()
T = int(input())
head = None
for i in range(T):
data = int(input())
head = mylist.insert(head, data)
mylist.display(head)
The advantage of this method is that we don't need to traverse the list each time we want to add a new node. The time complexity of the insert
function becomes O(1), which means that the function will have the same performance regardless of the size of the list.
Using the service like ChatGPT can help you tidy and clean up your code, making it easier to read and maintain. It can also help you spot logical errors or suggest improvements in your code structure. In fact source code 2 and 3 were generated by ChatGPT GPT4!
For more insightful solutions and tech-related content, feel free to connect with me on my Beacons page.
Top comments (0)