Bottom Page

Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
 FAST algorithm of checkSamecircularList(x, y) without L CircularList ref but find ref
#1
My book has this exercise:

R-7.6 Suppose that x and y are references to nodes of circularly linked lists,
although not necessarily the same list. Describe a fast algorithm for telling
if x and y belong to the same list.

I wonder if there is the FAST algorithm of checkSamecircularList(x, y) without L CircularList ref but find ref to L from the first element x... can do this??? after check if y is in this List of x... well ?

checkSamecircularList(L, x, y):
result

RESTART: F:/DOWNLOADS/Textbooks - Source Code/Python DS Tamassia/ch07/exe/R-7-6.py
same list x, y of L: True
same list x1, y of L: False
same list x1, y1 of L: False
same list x1, y1 of L1: True
>>>

if __name__ == '__main__':

    # Function to find sum of the given  
    # Circular linked list      
    def checkSamecircularList(L, x, y): 
      temp = L._tail   # head
      # tsum = temp.data 
      temp = temp._next

      xyes = False
      yyes = False

      while(temp is not L._tail):
        if temp is x:
          xyes = True
        if temp is y:
          yyes = True        
        temp = temp._next
      return xyes and yyes

  
    L = CircularQueue()
    L.enqueue(1)
    L.enqueue(2)
    L.enqueue(3)
    L.enqueue(4)
    L.enqueue(5)

    L1 = CircularQueue()
    L1.enqueue(1)
    L1.enqueue(2)
    L1.enqueue(3)
    L1.enqueue(4)
    L1.enqueue(5)

    x = L.first()
    y = (L.first())._next



    x1 = L1.first()
    y1 = (L1.first())._next

    
    print("same list x, y of L: " + str(checkSamecircularList(L, x, y)) )
    print("same list x1, y of L: " + str(checkSamecircularList(L, x1, y)) )
    print("same list x1, y1 of L: " + str(checkSamecircularList(L, x1, y1)) )
    print("same list x1, y1 of L1: " + str(checkSamecircularList(L1, x1,y1)) )
Quote

Top Page

Possibly Related Threads...
Thread Author Replies Views Last Post
  Fast get pixel and oparate. storzo 4 137 4 hours ago
Last Post: storzo
  fast lookup for array markB 3 229 May-13-2019, 12:11 AM
Last Post: scidam
  How can I make a faster search algorithm pianistseb 19 798 Apr-18-2019, 05:48 PM
Last Post: Larz60+
  Implementing a recursive algorithm for tree. Negativ3 3 473 Apr-10-2019, 10:43 PM
Last Post: Yoriz
  Cant get my head round the algorithm hshivaraj 1 165 Apr-09-2019, 10:38 PM
Last Post: Yoriz
  Check fast similarity between gps coordinates dervast 0 196 Apr-08-2019, 07:27 PM
Last Post: dervast
  To make an algorithm work faster pianistseb 3 328 Apr-01-2019, 08:42 AM
Last Post: Gribouillis
  Sorting algorithm issues Clunk_Head 2 315 Feb-17-2019, 03:58 AM
Last Post: Clunk_Head
  Genetic Algorithm rajeev1729 3 877 Jan-24-2019, 10:07 AM
Last Post: rajeev1729
  Algorithm effect on the CPU Faruk 3 352 Dec-19-2018, 08:57 AM
Last Post: Faruk

Forum Jump:


Users browsing this thread: 1 Guest(s)