"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.6 palindrome

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 isPalinedrome(head_node):
    reversed_node = reverseAndClone(head_node)
    return isEqual(head_node,reversed_node)

def reverseAndClone(node):
    head_node = None
    while node:
        n = Node(node.data)
        n.next = head_node
        head_node = n
        node = node.next
    
    return head_node

def isEqual(one,two):
    while one and two:
        if one.data != two.data:
            return False
        one = one.next
        two = two.next
    return one == None and two == None

dll_1 = DoublyLinkedList() 

# DLL: None -> 0(head) -> 1 -> 2 -> 1 -> 0(last) -> None 
dll_1.append(0)  
dll_1.append(1) 
dll_1.append(2) 
dll_1.append(1) 
dll_1.append(0)  

dll_1.printList(dll_1.head) 

print(isPalinedrome(dll_1.head))

dll_2 = DoublyLinkedList() 

# DLL: None -> 0(head) -> 1 -> 2 -> 1(last) -> None 
dll_2.append(0)  
dll_2.append(1) 
dll_2.append(2) 
dll_2.append(1) 

dll_2.printList(dll_2.head) 

print(isPalinedrome(dll_2.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 
  
    #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

    def printList(self, node): 
  
        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