DS Practice Problem

1-Problem
How do you reverse a singly linked list without recursion?

2-Problem
How do you find the third node from the end in a singly linked list?

3-Problem
How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle?

“It is your life, enjoy the smile, joy and freedom the way you want; but don’t forget your aim; temptations will be there to distract you; but the winner is one who stays focused always. All the best.”

**** Don’t forget to like the questions & comment on it !

Regards
Utkarsh Kesharwani

4 Likes
class Node:
    # Constructor to initialize the node object
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None
    #1
    def reverse(self):
        current = self.head
        prev = None
        while(current is not None):
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev
    #2
    def find_nth_last_node(self,n):
        current = self.head
        prev = self.head
        count = n-1
        while count:
            # print(f'current:{current.data}')
            current = current.next
            if current is None:
                print(f'{n}th node from end does not exists')
                return
            count-=1
        while(current.next is not None):
            current = current.next
            prev = prev.next
            # print(f'prev:{prev.data}')
            # print(f'current:{current.data}')
        return prev.data
    #3
    def isCycle(self):
        slow_ptr = self.head
        fast_ptr = self.head
        while(slow_ptr and fast_ptr and fast_ptr.next):
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next
            if slow_ptr == fast_ptr:
                slow_ptr = self.head
                while(slow_ptr != fast_ptr):
                    slow_ptr = slow_ptr.next
                    fast_ptr = fast_ptr.next
                print(f'Cycle Exists at {slow_ptr.data}')
                return
        print('Cycle does not exist')
        return

    def push(self,new_data):
        node = Node(new_data)
        node.next = self.head
        self.head = node
    
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data,end = ' ')
            temp = temp.next

llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
llist.push(35)
llist.push(50)

print ("Given Linked List")
llist.printList()
llist.reverse()
print ("\nReversed Linked List")
llist.printList()
print("\nThird node from the end")
llist.find_nth_last_node(1)
llist.isCycle()
1 Like