Day 15: Linked List | HackerRank

The House of Online Judge (63 Part Series)

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 is null 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:

Enter fullscreen mode Exit fullscreen mode

The Output

The function should return a reference to the head node of the linked list.

Sample Output:


2 3 4 1
2 3 4 1
2 3 4 1

Enter fullscreen mode Exit fullscreen mode

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.


<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span>
<span>class</span> <span>Solution</span><span>:</span> 
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span><span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span><span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>
    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>head</span><span>,</span><span>data</span><span>):</span> 
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>head</span><span>:</span>
            <span>tail</span> <span>=</span> <span>head</span>
            <span>while</span> <span>tail</span><span>.</span><span>next</span><span>:</span>
                <span>tail</span> <span>=</span> <span>tail</span><span>.</span><span>next</span>
            <span>tail</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
            <span>return</span> <span>head</span>
        <span>return</span> <span>node</span>
<span>mylist</span><span>=</span> <span>Solution</span><span>()</span>
<span>T</span><span>=</span><span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span><span>=</span><span>None</span>
<span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span><span>=</span><span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span><span>=</span><span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span><span>data</span><span>)</span>    
<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>);</span>
<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span>

<span>class</span> <span>Solution</span><span>:</span> 
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span><span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span><span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>

    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>head</span><span>,</span><span>data</span><span>):</span> 
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>head</span><span>:</span>
            <span>tail</span> <span>=</span> <span>head</span>
            <span>while</span> <span>tail</span><span>.</span><span>next</span><span>:</span>
                <span>tail</span> <span>=</span> <span>tail</span><span>.</span><span>next</span>
            <span>tail</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
            <span>return</span> <span>head</span>
        <span>return</span> <span>node</span>

<span>mylist</span><span>=</span> <span>Solution</span><span>()</span>
<span>T</span><span>=</span><span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span><span>=</span><span>None</span>
<span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span><span>=</span><span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span><span>=</span><span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span><span>data</span><span>)</span>    
<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>);</span>
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);

Enter fullscreen mode Exit fullscreen mode

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.


<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span>
<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span> <span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>
    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>,</span> <span>data</span><span>):</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>not</span> <span>head</span><span>:</span>
            <span>return</span> <span>node</span>
        <span>tail</span> <span>=</span> <span>head</span>
        <span>while</span> <span>tail</span><span>.</span><span>next</span><span>:</span>
            <span>tail</span> <span>=</span> <span>tail</span><span>.</span><span>next</span>
        <span>tail</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
        <span>return</span> <span>head</span>
<span>mylist</span> <span>=</span> <span>Solution</span><span>()</span>
<span>T</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span> <span>=</span> <span>None</span>
<span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span> <span>=</span> <span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span> <span>data</span><span>)</span>
<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>)</span>
<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span>

<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span> <span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>

    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>,</span> <span>data</span><span>):</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>not</span> <span>head</span><span>:</span>
            <span>return</span> <span>node</span>

        <span>tail</span> <span>=</span> <span>head</span>
        <span>while</span> <span>tail</span><span>.</span><span>next</span><span>:</span>
            <span>tail</span> <span>=</span> <span>tail</span><span>.</span><span>next</span>

        <span>tail</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
        <span>return</span> <span>head</span>

<span>mylist</span> <span>=</span> <span>Solution</span><span>()</span>
<span>T</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span> <span>=</span> <span>None</span>

<span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span> <span>=</span> <span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span> <span>data</span><span>)</span>

<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>)</span>
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)

Enter fullscreen mode Exit fullscreen mode

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:


<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span> 
<span>class</span> <span>Solution</span><span>:</span> 
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span><span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span><span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>
    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>head</span><span>,</span><span>data</span><span>):</span> 
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>not</span> <span>head</span><span>:</span>
            <span>self</span><span>.</span><span>tail</span> <span>=</span> <span>[</span><span>node</span><span>]</span>  <span># initialize the static variable </span>            <span>return</span> <span>node</span>
        <span>else</span><span>:</span>
            <span>self</span><span>.</span><span>tail</span><span>[</span><span>0</span><span>].</span><span>next</span> <span>=</span> <span>node</span>  <span># update the next attribute of the tail node </span>            <span>self</span><span>.</span><span>tail</span><span>[</span><span>0</span><span>]</span> <span>=</span> <span>node</span>  <span># update the tail node </span>            <span>return</span> <span>head</span>
<span>mylist</span> <span>=</span> <span>Solution</span><span>()</span>
<span>T</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span> <span>=</span> <span>None</span>
<span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span> <span>=</span> <span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span> <span>data</span><span>)</span>    
<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>)</span>
<span>class</span> <span>Node</span><span>:</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span><span>data</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>None</span> 

<span>class</span> <span>Solution</span><span>:</span> 
    <span>def</span> <span>display</span><span>(</span><span>self</span><span>,</span><span>head</span><span>):</span>
        <span>current</span> <span>=</span> <span>head</span>
        <span>while</span> <span>current</span><span>:</span>
            <span>print</span><span>(</span><span>current</span><span>.</span><span>data</span><span>,</span><span>end</span><span>=</span><span>' '</span><span>)</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>

    <span>def</span> <span>insert</span><span>(</span><span>self</span><span>,</span><span>head</span><span>,</span><span>data</span><span>):</span> 
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>not</span> <span>head</span><span>:</span>
            <span>self</span><span>.</span><span>tail</span> <span>=</span> <span>[</span><span>node</span><span>]</span>  <span># initialize the static variable </span>            <span>return</span> <span>node</span>
        <span>else</span><span>:</span>
            <span>self</span><span>.</span><span>tail</span><span>[</span><span>0</span><span>].</span><span>next</span> <span>=</span> <span>node</span>  <span># update the next attribute of the tail node </span>            <span>self</span><span>.</span><span>tail</span><span>[</span><span>0</span><span>]</span> <span>=</span> <span>node</span>  <span># update the tail node </span>            <span>return</span> <span>head</span>

<span>mylist</span> <span>=</span> <span>Solution</span><span>()</span>
<span>T</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
<span>head</span> <span>=</span> <span>None</span>
<span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>T</span><span>):</span>
    <span>data</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>())</span>
    <span>head</span> <span>=</span> <span>mylist</span><span>.</span><span>insert</span><span>(</span><span>head</span><span>,</span> <span>data</span><span>)</span>    
<span>mylist</span><span>.</span><span>display</span><span>(</span><span>head</span><span>)</span>
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)

Enter fullscreen mode Exit fullscreen mode

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!

Original Source

For more insightful solutions and tech-related content, feel free to connect with me on my Beacons page.

ranggakd – Link in Bio & Creator Tools | Beacons

@ranggakd | center details summary summary Oh hello there I m a an Programmer AI Tech Writer Data Practitioner Statistics Math Addict Open Source Contributor Quantum Computing Enthusiast details center.

beacons.ai

The House of Online Judge (63 Part Series)

原文链接：Day 15: Linked List | HackerRank | Python

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END