Created
July 16, 2018 04:12
-
-
Save shailendra9292/2dd231ab82298f54cc600c609e53b18c to your computer and use it in GitHub Desktop.
link list is palindrome or not in Python
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class node: | |
| def __init__(self, data=None): | |
| self.data = data | |
| self.next = None | |
| class linked_list: | |
| def __init__(self): | |
| self.head = None | |
| def insertBeg(self, data): | |
| temp = node(data) | |
| temp.next = self.head | |
| self.head = temp | |
| def compareList(self, headA , headB): | |
| while headA and headB and (headA.data == headB.data): | |
| headA = headA.next | |
| headB = headB.next | |
| return 1 if headA==headB else 0 | |
| def pallindrome(self,first_head,first_end,second_head,second_end): | |
| if self.length()== 1: | |
| print('Pallindrome') | |
| return | |
| first_end.next = None | |
| second_reverselist_head = self.reverse_list(second_head) | |
| res = self.compareList(first_head,second_reverselist_head) | |
| print("Pallindrome") if (res == 1) else print("Not Pallindrome") # python conditonal statement(ternary) | |
| def printList(self, head): | |
| p = head | |
| while p: | |
| print(p.data, end=' ') | |
| if p.next is not None: | |
| print('->', end=' ') | |
| p = p.next | |
| print() | |
| def reverse_list(self, head): | |
| if head is None or head.next is None : | |
| return head | |
| res = self.reverse_list(head.next) | |
| head.next.next = head | |
| head.next = None | |
| return res | |
| def middle_node(self): | |
| x = self.length() % 2 # check even-odd list | |
| p = self.head | |
| c = 1 | |
| if self.length()==1: | |
| return self.head,self.head,self.head,self.head | |
| # end pointer for second list | |
| last = self.head | |
| while last.next: | |
| last = last.next | |
| while p: | |
| if x != 0: # odd list | |
| if (self.length() // 2) == c: | |
| # return first and last node of both the list | |
| return self.head, p, p.next.next, last # drop middle element(p.next) for odd list | |
| c += 1 | |
| p = p.next | |
| elif x == 0: # even list | |
| if self.length() // 2 == c: | |
| # return first and last node of both the list | |
| return self.head, p, p.next, last | |
| c += 1 | |
| p = p.next | |
| def length(self): | |
| p = self.head | |
| c = 0 | |
| while p: | |
| c += 1 | |
| p = p.next | |
| return c | |
| l = linked_list() | |
| l.insertBeg(9) | |
| l.insertBeg(4) | |
| l.insertBeg(5) | |
| l.insertBeg(2) | |
| l.insertBeg(7) | |
| l.insertBeg(2) | |
| l.insertBeg(5) | |
| l.insertBeg(4) | |
| l.insertBeg(9) | |
| print("\nnode length is {} ".format(l.length())) | |
| print('list is....') | |
| l.printList(l.head) | |
| first_head,first_end, second_head,second_end= l.middle_node() | |
| l.pallindrome(first_head,first_end, second_head,second_end) | |
| print() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment