# class for the node
class ListNode(object):
def __init__(self,x):
self.val = x
self.next = None
def display(self):
printval = self
lists=[]
while printval is not None:
lists.append(printval.val)
printval = printval.next
print(lists)
# class for the linked list
class createLinkedList(object):
def __init__(self):
self.head = None
def insert(self,lists):
head = self
for i in range(0,len(lists)):
if i==0:
node = ListNode(lists[0])
self.head = node
else:
node.next = ListNode(lists[i])
node = node.next
# Print the linked list
def display(self):
printval = self.head
lists=[]
while printval is not None:
lists.append(printval.val)
printval = printval.next
print(lists)
234. Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2 Output: false Example 2:
Input: 1->2->2->1 Output: true
def isPalindrome(head):
"""
:head ListNode
step1 : save the list
step2 : compare
"""
stack = []
while head:
stack.append(head.val)
head = head.next
#return stack[::-1] == stack
return all(stack[i] == stack[-(i+1)] for i in range(len(stack)//2))
LinkedList = createLinkedList()
LinkedList.insert([1,2,2,1])
LinkedList.display()
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
isPalindrome(LinkedList.head)
LinkedList = createLinkedList()
LinkedList.insert([1,2,1,2])
LinkedList.display()
isPalindrome(LinkedList.head)
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2 Output: 1->2 Example 2:
Input: 1->1->2->3->3 Output: 1->2->3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head == None:
return head
prev_node = head
curr_node = head.next
while curr_node:
if curr_node.val == prev_node.val:
prev_node.next = curr_node.next
curr_node = curr_node.next
# in the case the last two are the same
else:
prev_node = prev_node.next
curr_node = curr_node.next
return head
LinkedList = createLinkedList()
LinkedList.insert([1,2,3,3])
LinkedList.display()
delete the duplicate element in place
Solution().deleteDuplicates(LinkedList.head)
LinkedList.display()
LinkedList = createLinkedList()
LinkedList.insert([1,1,2,3,3])
LinkedList.display()
Solution().deleteDuplicates(LinkedList.head)
LinkedList.display()
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
# recursively
class Solution:
def reverseList(self, head):
prev = None
current = head
while current:
temp = current.next
current.next = prev
prev = current
current = temp
return prev
LinkedList = createLinkedList()
LinkedList.insert([1,2,3,4,5])
LinkedList.display()
Solution().reverseList(LinkedList.head)
LinkedList.display()
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input:
Output: 1->1->2->3->4->4
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
LinkedList1 = createLinkedList()
LinkedList2 = createLinkedList()
LinkedList1.insert([1,2,4])
LinkedList2.insert([1,3,4])
LinkedList1.display(),LinkedList2.display()
Solution().mergeTwoLists(LinkedList1.head,LinkedList2.head).display()