Runtime Error in "Removing loop from Linked List"

user_14186228 0
Viewed 220

I am trying the following code challenge:

You are given a linked list of N nodes. The task is to remove the loop from the linked list, if present.

Note: C is the position of the node to which the last node is connected. If it is 0 then no loop.

Example 1:

Input:

N = 3
value[] = {1,3,4}
C = 2

Output: 1

Explanation: In the first test case N = 3.The linked list with nodes N = 3 is given. Here, x = 2 which means last node is connected with xth node of linked list. Therefore, there exists a loop.

Example 2:

Input:

N = 4
value[] = {1,8,3,4}
C = 0

Output: 1

Explanation: N = 4 and x = 0, which means lastNode->next = NULL, thus the Linked list does not contains any loop.

Your Task:

Your task is to complete the function removeLoop(). The only argument of the function is head pointer of the linked list. Simply remove the loop in the list (if present) without disconnecting any nodes from the list. The driver code will print 1 if your code is correct.

Expected time complexity : O(n)

Expected auxiliary space : O(1)

Constraints:

1 <= N <= 104

My Code:

'''
class Node:
    def __init__(self,val):
        self.next=None
        self.data=val
'''

def removeLoop(head):
    slow = fast = head
    while fast!=None and fast.next!=None:
        slow = slow.next
        fast = fast.next.next
        if slow==fast:
            x = slow
    temp = head
    while x.next!=temp.next:
        x = x.next
        temp = temp.next
    x.next = None
    return head

I am getting a Runtime Error. Can anyone tell me why?

linked-list algorithm python
1 Answers

There are a few issues:

  • When the list has no cycle, then x is undefined at

      while x.next!=temp.next:

  • When the list has a cycle, the first loop never exits.

  • When the cycle includes all nodes (the "tail" links back to the first node), then this code will break the link between the head node and the second node, which obviously is wrong. This is a boundary case which requires a separate solution.

The first two problems drill down to an indentation problem. The second while loop should be executed only when a cycle was detected. The easiest is to just move it inside the if that detected the cycle, together with the return statement:

def removeLoop(head):
    slow = fast = head
    while fast!=None and fast.next!=None:
        slow = slow.next
        fast = fast.next.next
        if slow==fast:
            if slow == head:  # special case
                # find the "tail" node
                while slow.next != head:
                    slow = slow.next
            else:
                while slow.next != head.next:
                    slow = slow.next
                    head = head.next
            slow.next = None
            return

To my understanding no value needs to be returned, so no need to return head.

Example run

Here is the code completed with some boilerplate code, and a run for the following problem:

N = 5
value[] = {7,58,36,34,16}
C = 1

So that represents the following list with a cycle:

7 → 58 → 36
↑         ↓
16   ←   34

The removeLoop function will remove the link between 16 and 7.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def print(self):
        node = self
        for _ in range(10):
            if not node:
                break
            print(node.val, end=" ")
            node = node.next
        print("..." if node else "")

def createLinkedList(values, cycle_start_index):
    # create all nodes
    nodes = [Node(val) for val in values]
    for i, node in enumerate(nodes):
        if i:  # link node from previous
            nodes[i-1].next = node
    if cycle_start_index > 0:  # create the cycle
        nodes[-1].next = nodes[cycle_start_index-1]  # 1-based index
    return nodes[0]

def removeLoop(head):
    slow = fast = head
    while fast!=None and fast.next!=None:
        slow = slow.next
        fast = fast.next.next
        if slow==fast:
            if slow == head:  # special case
                # find the "tail" node
                while slow.next != head:
                    slow = slow.next
            else:
                while slow.next != head.next:
                    slow = slow.next
                    head = head.next
            slow.next = None
            return

# demo
lst = createLinkedList([7, 58, 36, 34, 16], 1)
lst.print()  # 7 58 36 34 16 58 36 34 16 58 ...
removeLoop(lst)
lst.print()  # 7 58 36 34 16
user_54598390
Related