4165 – FinserareKX

Enunţ

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

   struct Nod
   {
     int info;
     Nod *leg;
   };

în care câmpul info memorează un număr întreg, iar câmpul leg memorează adresa următorului element al listei.

Cerinţa

Să se scrie o funcție C++ cu următorul prototip:

   void FInserareKX(Nod * &head, int k, int x);

care, în lista pentru care primul element are adresa memorată în pointerul head, inserează pe poziția k un nou nod cu informația x. Dacă lista are mai puțin de k noduri, inserarea se face la sfârșitul listei, iar dacă k ≤ 1, atunci inserarea se va face la începutul listei. Lista poate fi inițial și vidă, caz în care head = NULL. De exemplu, dacă lista conține inițial informațiile 1, 2, 3, 4, 5, k = 3 și x = 100, atunci lista devine: 1, 2, 100, 3, 4, 5.

Important

Rezolvarea se va face în python. Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Rezolvare

#4165 FInserareKX
class Node:
  def __init__(self, info):
    self.info = info
    self.next = None

def FInserareKX(head, k, x):
  new_node = Node(x)
  
  # Cazul în care lista este inițial vidă sau inserăm la începutul listei
  if head is None or k <= 1:
    new_node.next = head
    head = new_node
    return head
  
  # Cazul în care lista are cel puțin un nod și inserăm pe poziția k sau la sfârșitul listei
  current = head
  prev = None
  count = 1
  
  while current and count < k:
    prev = current
    current = current.next
    count += 1
  
  if current is None:  # Inserare la sfârșitul listei
    prev.next = new_node
  else:  # Inserare pe poziția k
    new_node.next = current
    prev.next = new_node
  
  return head

# Funcție pentru afișarea listei
def afisare_lista(head):
  current = head
  while current:
    print(current.info, end=" ")
    current = current.next
  print()

# Exemplu de utilizare
if __name__ == "__main__":
  # Inițializare lista cu câteva noduri
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  
  # Inserare pe poziția k = 3 a valorii x = 100
  head = FInserareKX(head, 3, 100)
  
  # Afișare lista rezultată
  afisare_lista(head)