Основи програмирања: вежбе - XIII недеља
Задатак 1
За дат почетак повезане листе, одредити да ли повезана листа има петљу. Повезана листа има петљу ако можемо да дођемо до неког чвора поново пратећи следеће чворове. Вратити True ако постоји петља у повезној листи, у супротном вратити False.
Решење - $O(N)$ меморија
# Дефиниција чвора листе:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(self, head):
skup_vidjenih = set()
curr = head
while curr:
if curr in skup_vidjenih:
return True
else:
skup_vidjenih.add(curr)
curr = curr.next
return False
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
##head.next.next.next.next = head.next
#print(head.hasCycle(head))
Решење - $O(1)$ меморија
# Дефиниција чвора листе:
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def hasCycle(self, head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#head.next.next.next.next = head.next
#print(head.hasCycle(head))
Задатак 2
За дат почетак повезане листе, вратити чвор у средини повезане листе. Ако повезана листа има паран број чворова, вратити други у средини.
Решење - један пролаз кроз листу
# Дефиниција чвора листе.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def middleNode(self, head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Решење - два пролаза кроз листу
# Дефиниција чвора листе.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def middleNode(self, head):
# тражимо дужину листе
curr = head
duzina = 0
while curr:
duzina+=1
curr=curr.next
# прелазимо до половине листе
curr = head
for i in range(duzina//2):
curr=curr.next
return curr
Задатак 3
За дат почетак сортиране повезане листе, избацити чворове тако да се свака вредност појављује само једном, и вратити нови почетак.
Решење без $dummy$ чвора
# Дефинисија чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(self, head):
curr = head
while curr and curr.next:
if curr.val == curr.next.val:
curr.next = curr.next.next
else:
curr = curr.next
return head
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(4)
#head.next.next.next = ListNode(6)
#head.next.next.next.next = ListNode(6)
#head = ListNode(2, ListNode(4, ListNode(4, ListNode(6, ListNode(6)))))
#newHead = head.deleteDuplicates(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
Решење са $dummy$ чвором
# Дефинисија чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(self, head):
dummy = ListNode(float('inf'),head)
prev, curr = dummy, head
while curr:
if prev.val == curr.val:
prev.next = curr.next
else:
prev = prev.next
curr = curr.next
return dummy.next
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(4)
#head.next.next.next = ListNode(6)
#head.next.next.next.next = ListNode(6)
#newHead = head.deleteDuplicates(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
Задатак 4
За дат почетак повезане листе, избрисати н-ти чвор са краја листе, и вратити нови почетак листе.
Решење - два пролаза кроз листу
# Дефиниција чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head,n):
curr = head
duzina = 0
while curr:
duzina+=1
curr = curr.next
dummy = ListNode(0,head)
prev, curr = dummy, head
for i in range(duzina - n):
prev = curr
curr = curr.next
prev.next = curr.next
return dummy.next
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#newHead = removeNthFromEnd(head, 2)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
Решење - један пролаз кроз листу
# Дефиниција чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head,n):
fast = head
for i in range(n):
fast = fast.next
dummy = ListNode(val=0,next=head)
prev, curr= dummy, head
while fast:
prev = curr
curr = curr.next
fast = fast.next
prev.next = curr.next
return dummy.next
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#newHead = removeNthFromEnd(head, 2)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
Задатак 5
За дата два почетка повезаних листи, вратити први њихов заједнички чвор. Уколико немају заједнички чвор, вратити None.
Решење - $O(N)$ меморија
# Дефиниција чвора листе.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
def getIntersectionNode(headA, headB):
# пролазимо кроз листу А и чувамо све чворове у скуп
skup_vidjenih = set()
while headA:
skup_vidjenih.add(headA)
headA = headA.next
# пролазимо кроз листу B и када наиђемо на чвор који је у скупу
# то је први заједнички
while headB:
if headB in skup_vidjenih:
return headB
skup_vidjenih.add(headB)
headB = headB.next
return None
Решење - $O(1)$ меморија
# Дефиниција чвора листе.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
ddef getIntersectionNode(headA, headB):
# израчунај дужину листе A
lA, curr = 0, headA
while curr:
lA+=1
curr=curr.next
# израчунај дужину листе B
lB, curr = 0, headB
while curr:
lB+=1
curr=curr.next
# за дужи, head пребаци за разлику места
if lA > lB:
for i in range(lA-lB):
headA = headA.next
if lA < lB:
for i in range(-(lA-lB)):
headB = headB.next
# крећемо од новог head-a и старог head-a
# скачемо за једно место
# и када су једнаки, ту се секу
while headA and headB:
if headA == headB:
return headA
headA = headA.next
headB = headB.next
return None
Задатак 6
За дат почетак повезане листе, вратити почетак изокренуте листе.
Рекуризвно решење
# Дефиниција чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
if head ==None or head.next == None:
return head
newHead = head.next
if head.next:
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#newHead = reverseList(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
#print(newHead.next.next.next.val)
Итеративно решење
# Дефиниција чвора листе:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev, curr = None, head
while curr:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
return prev
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#newHead = reverseList(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
#print(newHead.next.next.next.val)
Задатак 7
За дат почетак повезане листе, вратити True ако је листа палиндром у супротном вратити False.
Решење
# Дефинисија чвора листе.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def isPalindrome(self, head):
# nadjemo polovinu
slow,fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
#od polovine do kraja izokrenemo
prev, curr = None, slow
while curr:
tmp = curr.next
curr.next = prev
prev = curr
curr = tmp
# gledamo cvor po cvor od pocetka i kraja
# i uporedjujemo vrednosti
left, right = head, prev
while left and right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True