"Book to train programming skills to fight in the world" Python code answer example --2.7 intersecting nodes

"Book to train programming skills to fight in the world" Python code answer example --2.7 intersecting nodes

CHAP2. Linked list

  1. Remove duplicate elements
  2. Return Kth from the back
  3. Remove elements between
  4. Split list
  5. Sum of two numbers represented in the list
  6. Palindrome
  7. Intersecting nodes

Python code answer example

python



from chap2_function import* 

def dll_from_node(node): 
  
    dll = DoublyLinkedList()

    while(node is not None): 
        dll.append(node.data) 
        last = node 
        node = node.next

    return dll

class Result:
    
    #constructor
    def __init__(self, tail, size):
        self.tail = tail
        self.size = size 

def findIntersection(list1,list2):

    if list1 == None or list2 == None:
        return None

    result1 = getTailAndSize(list1)
    result2 = getTailAndSize(list2)

    if result1.tail != result2.tail:
        return None
    
    shorter = list1 if result1.size < result2.size else list2
    longer = list2 if result1.size < result2.size else list1

    longer = getKthNode(longer,abs(result1.size-result2.size))

    while shorter.data != longer.data:
        shorter = shorter.next
        longer = longer.next

    return longer

def getTailAndSize(list_node):

    if list_node == None:
        return None

    size = 1
    current = list_node

    while current.next:
        size = size + 1
        current = current.next
    
    return Result(current,size)

def getKthNode(head_node,k):
    
    current = head_node

    while k>0 and current:
        current = current.next
        k = k - 1

    return current

dll_1 = DoublyLinkedList() 

# DLL: None -> 3(head) -> 1 -> 5 -> 9 -> 7 -> 2 ->1(last) -> None 
dll_1.append(3)  
dll_1.append(1) 
dll_1.append(5) 
dll_1.append(9) 
dll_1.append(7)  
dll_1.append(2) 
dll_1.append(1) 

dll_1.printList(dll_1.head) 

dll_2 = DoublyLinkedList() 

# DLL: None -> 4(head) -> 6 -> 7 -> 2 ->1(last) -> None 
dll_2.append(4)  
dll_2.append(6) 
dll_2.insertNode(dll_2.head.next,dll_1.head.next.next.next.next)

dll_2.printList(dll_2.head) 

result_dll = dll_from_node(findIntersection(dll_1.head,dll_2.head))
result_dll.printList(result_dll.head)

Python functions (node class, bidirectional list class)

chap2_function.py


#Node class
class Node: 
  
    #constructor
    def __init__(self, data): 
        self.data = data 
        self.next = None
        self.prev = None
  
#Bidirectional list class
class DoublyLinkedList: 
  
    #constructor
    def __init__(self): 
        self.head = None
  
    #Node insertion from the first node
    def push(self, new_data): 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Make the next node of the new node the head node in the first place
        new_node.next = self.head 
  
        #Although it was a head node in the first place, the previous node is changed to a new node
        if self.head is not None: 
            self.head.prev = new_node 
  
        #Make the new node a head node
        self.head = new_node 
  
    #Insert node at waypoint
    def insert(self, prev_node, new_data): 
  
        # prev_Specify whether to insert the node after the node specified by node
        #If None, exit the function
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Prev the next node of the new node_Make it the next node of the node specified by node
        new_node.next = prev_node.next
  
        # prev_Makes the next node of the node specified by node a new node
        prev_node.next = new_node 
  
        #Prev the previous node of the new node_Make it the node specified by node
        new_node.prev = prev_node 
  
        #Prev the next node of the new node_I made it the next node of the node specified by node, but the previous node of that node is also made a new node
        if new_node.next is not None: 
            new_node.next.prev = new_node 

    def insertNode(self, prev_node, new_node): 
  
        # prev_Specify whether to insert the node after the node specified by node
        #If None, exit the function
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
        
        if new_node is None: 
            print("the given new node cannot be NULL")
            return 
  
        # prev_Makes the next node of the node specified by node a new node
        prev_node.next = new_node 
  
        #Prev the previous node of the new node_Make it the node specified by node
        new_node.prev = prev_node 
  
  
    #Insert node from last node
    def append(self, new_data): 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Define the next node of the new node to None
        new_node.next = None
  
        #If no head node is set (empty list), set a new node as the head node
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        #Set the final node (forward scanning)
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        #Designate a new node as the last node
        last.next = new_node 
  
        # 7.Make the previous node of the new node the last node in the first place
        new_node.prev = last 
  
        return
  
    def delete(self,del_node):

        if self.head == None or del_node == None: 
            return 

        if self.head == del_node: 
            self.head = del_node.next

        if del_node.next != None: 
            del_node.next.prev = del_node.prev 

        if del_node.prev != None: 
            del_node.prev.next = del_node.next

    # This function prints contents of linked list 
    # starting from the given node 
    def printList(self, node): 

        last = None
  
        print("Bidirectional list: \n") 

        print("Forward scanning")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  
        print("Reverse scanning")
        while(last is not None): 
            print(last.data,end="")
            last = last.prev 
            if last:
                print(" -> ",end="")
            else:
                print("\n")
  
if __name__ == '__main__':
    #Generate an empty bidirectional list
    # DLL: None
    dll = DoublyLinkedList() 
    # DLL: None -> 6(head/last) -> None
    dll.append(6) 
    # DLL: None -> 7(head) -> 6(last) -> None 
    dll.push(7) 
    # DLL: None -> 1(head) -> 7 -> 6(last) -> None 
    dll.push(1) 
    # DLL: None -> 1(head) -> 7 -> 6 -> 4(last) -> None 
    dll.append(4) 
    # DLL: None -> 1(head) -> 7 -> 8 -> 6 -> 4(last) -> None 
    dll.insert(dll.head.next, 8) 
    # DLL: None -> 1(head) -> 8 -> 6 -> 4(last) -> None 
    dll.delete(dll.head.next) 

    dll.printList(dll.head) 

References

[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List

Recommended Posts

"Book to train programming skills to fight in the world" Python code answer example --2.7 intersecting nodes
"Book to train programming skills to fight in the world" Python code answer example --1.3 URLify
"Book to train programming skills to fight in the world" Python code answer example --2.6 palindrome
"Book to train programming skills to fight in the world" Python code answer example --2.4 Splitting the list
"A book to train programming skills to fight in the world" Python code answer example --1.8 "0" matrix
"A book to train programming skills to fight in the world" Python code answer example --3.1 Three stacks
"Book to train programming skills to fight in the world" Python code answer example --1.4 Permutation of sentences
"A book to train programming skills to fight in the world" Python code answer example --1.1 Duplicate character string
"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back
"A book to train programming skills to fight in the world" Python code Solution example --1.6 String compression
"A book to train programming skills to fight in the world" Python code solution example --1.5 One-shot conversion
"A book to train programming skills to fight in the world" Python code Solution example --1.7 Matrix rotation
"A book to train programming skills to fight in the world" Python code Solution example --2.8 Loop detection
"Book to train programming skills to fight in the world" Python code solution example --- Removed elements between 2.3
"Book to train programming skills to fight in the world" Python code Solution example --2.1 Remove duplicate elements
"A book to train programming skills to fight in the world" Python code answer example --1.2 Count the number of the same characters
"A book to train programming skills to fight in the world" Python code Solution example --2.5 The sum of two numbers shown in the list
Programming to fight in the world ~ 5-1
Programming to fight in the world ~ 5-5,5-6
Programming to fight in the world 5-3
Programming to fight in the world ~ 5-2
Programming to fight in the world-Chapter 4
An example of the answer to the reference question of the study session. In python.
[Kenchon book to Python] "Train your problem-solving skills! Algorithms and data structures" I tried to rewrite the posted code in Python! -table of contents-
[Kenchon book to Python]-Chapter 3- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python]-Chapter 2- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python]-Chapter 4-"Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
Try to solve the programming challenge book with python3
[Python] PCA scratch in the example of "Introduction to multivariate analysis"
I wrote the code to write the code of Brainf * ck in python
In the python command python points to python3.8
Sample code to get the Twitter API oauth_token and oauth_token_secret in Python 2.7
What kind of book is the best-selling "Python Crash Course" in the world?
Tips for Python beginners to use the Scikit-image example for themselves 6 Improve Python code
Part 1 I wrote an example of the answer to the reference problem of how to write offline in real time in Python
Get the EDINET code list in Python
How to display Hello world in python
I stumbled on the character code when converting CSV to JSON in Python
I searched for the skills needed to become a web engineer in Python
How to use the C library in Python
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Personal notes to doc Python code in Sphinx
To dynamically replace the next method in python
Say hello to the world with Python with IntelliJ
Draw graphs in Julia ... Leave the graphs to Python
The trick to write flatten concisely in python
How to get the files in the [Python] folder
I want to display the progress in Python!
Convert cubic mesh code to WKT in Python
Run the output code with tkinter, saying "A, pretending to be B" in python
[Note] How to write QR code and description in the same image with python
I used Python to find out about the role choices of the 51 "Yachts" in the world.