logo

TechCodeview

Bağlantılı listenin ortasını sil

Tek bağlantılı bir liste göz önüne alındığında, görev listenin orta düğümünü silmektir.

  • Liste eşit sayıda düğüm içeriyorsa, iki orta düğüm olacaktır. Bu durumda ikinci orta düğümü silin.
  • Bağlantılı liste yalnızca bir düğümden oluşuyorsa, NULL döndürün.

Örnek:



Giriş: LinkedList: 1-> 2-> 3-> 4-> 5
Çıktı: 1-> 2-> 4-> 5
Açıklama:

Bağlantılı listenin ortasını sil

Giriş: LinkedList: 2-> 4-> 6-> 7-> 5-> 1
Çıktı: 2-> 4-> 6-> 5-> 1
Açıklama:

Bağlantılı listenin ortasını sil

Giriş: LinkedList: 7
Çıktı:



if else if else if java

İçerik Tablosu

[Saf yaklaşım] İki geçişli geçiş - o (n) zaman ve o (1) boşluk

Bu yaklaşımın arkasındaki temel fikir, önce toplam düğüm sayısını saymak için bağlantılı listenin tamamını geçmektir. Toplam düğüm sayısını bildikten sonra, indeksli orta düğümün konumunu hesaplayabiliriz N/2 (burada n toplam düğüm sayısıdır). Sonra bağlantılı listeyi tekrar inceleyin, ancak bu sefer orta düğümden hemen önce dururuz. Oraya girdikten sonra, orta düğümden önce düğümün bir sonraki işaretçisini, orta düğümün üzerinden geçip doğrudan düğüme işaret etmesi için değiştiririz

Aşağıda yukarıdaki yaklaşımın uygulanmasıdır:



C++ 
// C++ program to delete middle of a linked list #include    using namespace std; struct Node {  int data;  Node* next;  Node(int x){  data = x;  next = nullptr;  } }; // Function to delete middle node from linked list. Node* deleteMid(Node* head) {  // Edge case: return nullptr if there is only  // one node.  if (head->next == nullptr)  return nullptr;  int count = 0;  Node *p1 = head *p2 = head;  // First pass count the number of nodes  // in the linked list using 'p1'.  while (p1 != nullptr) {  count++;  p1 = p1->next;  }  // Get the index of the node to be deleted.  int middleIndex = count / 2;  // Second pass let 'p2' move toward the predecessor  // of the middle node.  for (int i = 0; i < middleIndex - 1; ++i)  p2 = p2->next;  // Delete the middle node and return 'head'.  p2->next = p2->next->next;  return head; } void printList(Node* head) {  Node* temp = head;  while (temp != nullptr) {  cout << temp->data << ' -> ';  temp = temp->next;  }  cout << 'nullptr' << endl; } int main() {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5.  Node* head = new Node(1);  head->next = new Node(2);  head->next->next = new Node(3);  head->next->next->next = new Node(4);  head->next->next->next->next = new Node(5);  cout << 'Original Linked List: ';  printList(head);  // Delete the middle node.  head = deleteMid(head);  cout << 'Linked List after deleting the middle node: ';  printList(head);  return 0; }
C 
// C program to delete middle of a linked list #include  #include  struct Node {  int data;  struct Node* next; }; // Function to delete middle node from linked list. struct Node* deleteMid(struct Node* head) {  // Edge case: return NULL if there is only  // one node.  if (head->next == NULL)  return NULL;  int count = 0;  struct Node *p1 = head *p2 = head;  // First pass count the number of nodes  // in the linked list using 'p1'.  while (p1 != NULL) {  count++;  p1 = p1->next;  }  // Get the index of the node to be deleted.  int middleIndex = count / 2;  // Second pass let 'p2' move toward the predecessor  // of the middle node.  for (int i = 0; i < middleIndex - 1; ++i)  p2 = p2->next;  // Delete the middle node and return 'head'.  p2->next = p2->next->next;  return head; } void printList(struct Node* head) {  struct Node* temp = head;  while (temp != NULL) {  printf('%d -> ' temp->data);  temp = temp->next;  }  printf('NULLn'); } struct Node* newNode(int x) {  struct Node* temp =   (struct Node*)malloc(sizeof(struct Node));  temp->data = x;  temp->next = NULL;  return temp; } int main() {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5.  struct Node* head = newNode(1);  head->next = newNode(2);  head->next->next = newNode(3);  head->next->next->next = newNode(4);  head->next->next->next->next = newNode(5);  printf('Original Linked List: ');  printList(head);  // Delete the middle node.  head = deleteMid(head);  printf('Linked List after deleting the middle node: ');  printList(head);  return 0; }
Java 
// Java program to delete middle of a linked list class Node {  int data;  Node next;  Node(int x) {  data = x;  next = null;  } } public class GfG {  // Function to delete middle node from linked list.  public static Node deleteMid(Node head) {  // Edge case: return null if there is only  // one node.  if (head.next == null)  return null;  int count = 0;  Node p1 = head p2 = head;  // First pass count the number of nodes  // in the linked list using 'p1'.  while (p1 != null) {  count++;  p1 = p1.next;  }  // Get the index of the node to be deleted.  int middleIndex = count / 2;  // Second pass let 'p2' move toward predecessor  // of the middle node.  for (int i = 0; i < middleIndex - 1; ++i)  p2 = p2.next;  // Delete the middle node and return 'head'.  p2.next = p2.next.next;  return head;  }  public static void printList(Node head) {  Node temp = head;  while (temp != null) {  System.out.print(temp.data + ' -> ');  temp = temp.next;  }  System.out.println('null');  }  public static void main(String[] args) {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5.  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  System.out.print('Original Linked List: ');  printList(head);  // Delete the middle node.  head = deleteMid(head);  System.out.print  ('Linked List after deleting the middle node: ');  printList(head);  } }
Python 
# Python3 program to delete middle of a linked list class Node: def __init__(self data): self.data = data self.next = None # Function to delete middle node from linked list. def deleteMid(head): # Edge case: return None if there is only # one node. if head.next is None: return None count = 0 p1 = head p2 = head # First pass count the number of nodes # in the linked list using 'p1'. while p1 is not None: count += 1 p1 = p1.next # Get the index of the node to be deleted. middleIndex = count // 2 # Second pass let 'p2' move toward the predecessor # of the middle node. for i in range(middleIndex - 1): p2 = p2.next # Delete the middle node and return 'head'. p2.next = p2.next.next return head def printList(head): temp = head while temp is not None: print(temp.data end=' -> ') temp = temp.next print('None') if __name__ == '__main__': # Create a static hardcoded linked list: # 1 -> 2 -> 3 -> 4 -> 5. 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) print('Original Linked List:' end=' ') printList(head) # Delete the middle node. head = deleteMid(head) print('Linked List after deleting the middle node:' end=' ') printList(head)
C# 
// C# program to delete middle of a linked list using System; class Node {  public int data;  public Node next;  public Node(int x) {  data = x;  next = null;  } } class GfG {  // Function to delete middle node from linked list.  static Node deleteMid(Node head) {  // Edge case: return null if there is only  // one node.  if (head.next == null)  return null;  int count = 0;  Node p1 = head p2 = head;  // First pass count the number of nodes  // in the linked list using 'p1'.  while (p1 != null) {  count++;  p1 = p1.next;  }  // Get the index of the node to be deleted.  int middleIndex = count / 2;  // Second pass let 'p2' move toward the predecessor  // of the middle node.  for (int i = 0; i < middleIndex - 1; ++i)  p2 = p2.next;  // Delete the middle node and return 'head'.  p2.next = p2.next.next;  return head;  }  static void printList(Node head) {  Node temp = head;  while (temp != null) {  Console.Write(temp.data + ' -> ');  temp = temp.next;  }  Console.WriteLine('null');  }  static void Main(string[] args) {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5.  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  Console.Write('Original Linked List: ');  printList(head);  // Delete the middle node.  head = deleteMid(head);  Console.Write  ('Linked List after deleting the middle node: ');  printList(head);  } }
JavaScript 
class Node {  constructor(data) {  this.data = data;  this.next = null;  } } // Function to delete middle node from linked list. function deleteMid(head) {  // Edge case: return null if there is only  // one node.  if (head.next === null)  return null;  let count = 0;  let p1 = head p2 = head;  // First pass count the number of nodes  // in the linked list using 'p1'.  while (p1 !== null) {  count++;  p1 = p1.next;  }  // Get the index of the node to be deleted.  let middleIndex = Math.floor(count / 2);  // Second pass let 'p2' move toward the predecessor  // of the middle node.  for (let i = 0; i < middleIndex - 1; ++i)  p2 = p2.next;  // Delete the middle node and return 'head'.  p2.next = p2.next.next;  return head; } function printList(head) {  let temp = head;  while (temp !== null) {  console.log(temp.data + ' -> ');  temp = temp.next;  }  console.log('null'); } // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5. let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); console.log('Original Linked List: '); printList(head); // Delete the middle node. head = deleteMid(head); console.log('Linked List after deleting the middle node: '); printList(head);

Çıktı 
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr Linked List after deleting the middle node: 1 -> 2 -> 4 -> 5 -> nullptr

Zaman karmaşıklığı: Açık). Bağlantılı listenin iki geçişi gereklidir
Yardımcı Alan: O (1). Ekstra alana gerek yoktur.

[Beklenen Yaklaşım] Yavaş ve hızlı işaretçilerle tek geçişli geçiş - O (N) Zaman ve O (1) Alan

Yukarıdaki çözüm, bağlantılı listenin iki geçişini gerektirir. Orta düğüm bir geçiş kullanılarak silinebilir. Fikir iki işaret kullanmaktır Slow_ptr Ve fast_ptr . Hızlı işaretçi bir seferde iki düğümü hareket ettirirken, yavaş işaretçi aynı anda bir düğümü hareket ettirir. Hızlı işaretçi listenin sonuna ulaştığında yavaş işaretçi orta düğümde konumlandırılır. Ardından, orta düğümden önce gelen düğümü bağlamanız gerekir ( önsöz ) orta düğümden sonra gelen düğüme. Bu, listeden kaldırarak orta düğümü etkili bir şekilde atlar.

Java dizesinin uzunluğu

Aşağıda yukarıdaki yaklaşımın uygulanması

C++ 
// C++ program to delete middle of a linked list #include    using namespace std; struct Node {  int data;  Node* next;  Node(int x){  data = x;  next = nullptr;  } }; // Function to delete middle node from linked list struct Node* deleteMid(struct Node* head) {  // If the list is empty return NULL  if (head == NULL)  return NULL;  // If the list has only one node  // delete it and return NULL  if (head->next == NULL) {  delete head;  return NULL;  }  struct Node* prev = NULL;  struct Node* slow_ptr = head;  struct Node* fast_ptr = head;  // Move the fast pointer 2 nodes ahead  // and the slow pointer 1 node ahead  // until fast pointer reaches end of the list  while (fast_ptr != NULL && fast_ptr->next != NULL) {  fast_ptr = fast_ptr->next->next;   // Update prev to hold the previous   // slow pointer value  prev = slow_ptr;   slow_ptr = slow_ptr->next;   }  // At this point slow_ptr points to middle node  // Bypass the middle node  prev->next = slow_ptr->next;  // Delete the middle node  delete slow_ptr;   // Return the head of the modified list  return head; } void printList(struct Node* head) {  struct Node* temp = head;  while (temp != NULL) {  cout << temp->data << ' -> ';  temp = temp->next;  }  cout << 'NULL' << endl; } int main() {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5  Node* head = new Node(1);  head->next = new Node(2);  head->next->next = new Node(3);  head->next->next->next = new Node(4);  head->next->next->next->next = new Node(5);  cout << 'Original Linked List: ';  printList(head);  // Delete the middle node  head = deleteMid(head);  cout << 'Linked List after deleting the middle node: ';  printList(head);  return 0; }
C 
// C program to delete middle of a linked list #include  #include  struct Node {  int data;  struct Node* next; }; // Function to delete middle node from linked list struct Node* deleteMid(struct Node* head) {  // If the list is empty return NULL  if (head == NULL)  return NULL;  // If the list has only one node  // delete it and return NULL  if (head->next == NULL) {  free(head);  return NULL;  }  struct Node* prev = NULL;  struct Node* slow_ptr = head;  struct Node* fast_ptr = head;  // Move the fast pointer 2 nodes ahead  // and the slow pointer 1 node ahead  // until fast pointer reaches end of the list  while (fast_ptr != NULL && fast_ptr->next != NULL) {  fast_ptr = fast_ptr->next->next;  // Update prev to hold the previous   // slow pointer value  prev = slow_ptr;  slow_ptr = slow_ptr->next;  }  // At this point slow_ptr points to middle node  // Bypass the middle node  prev->next = slow_ptr->next;  // Delete the middle node  free(slow_ptr);  // Return the head of the modified list  return head; } void printList(struct Node* head) {  struct Node* temp = head;  while (temp != NULL) {  printf('%d -> ' temp->data);  temp = temp->next;  }  printf('NULLn'); } struct Node* newNode(int x) {  struct Node* temp =   (struct Node*)malloc(sizeof(struct Node));  temp->data = x;  temp->next = NULL;  return temp; } int main() {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5.  struct Node* head = newNode(1);  head->next = newNode(2);  head->next->next = newNode(3);  head->next->next->next = newNode(4);  head->next->next->next->next = newNode(5);  printf('Original Linked List: ');  printList(head);  // Delete the middle node.  head = deleteMid(head);  printf('Linked List after deleting the middle node: ');  printList(head);  return 0; }
Java 
// Java program to delete the middle of a linked list class Node {  int data;  Node next;  Node(int x) {  data = x;  next = null;  } } class GfG {  // Function to delete middle node from linked list  static Node deleteMid(Node head) {  // If the list is empty return null  if (head == null)  return null;  // If the list has only one node  // delete it and return null  if (head.next == null) {  return null;  }  Node prev = null;  Node slow_ptr = head;  Node fast_ptr = head;  // Move the fast pointer 2 nodes ahead  // and the slow pointer 1 node ahead  // until fast pointer reaches end of list  while (fast_ptr != null   && fast_ptr.next != null) {  fast_ptr = fast_ptr.next.next;  // Update prev to hold the previous   // slow pointer value  prev = slow_ptr;  slow_ptr = slow_ptr.next;  }  // At this pointslow_ptr points to middle node  // Bypass the middle node  prev.next = slow_ptr.next;  // Return the head of the modified list  return head;  }    static void printList(Node head) {  Node temp = head;  while (temp != null) {  System.out.print(temp.data + ' -> ');  temp = temp.next;  }  System.out.println('NULL');  }    public static void main(String[] args) {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  System.out.print('Original Linked List: ');  printList(head);  // Delete the middle node  head = deleteMid(head);  System.out.print  ('Linked List after deleting the middle node: ');  printList(head);  } }
Python 
# Python program to delete the middle of a linked list class Node: def __init__(self data): self.data = data self.next = None # Function to delete middle node from linked list def deleteMid(head): # If the list is empty return None if head is None: return None # If the list has only one node # delete it and return None if head.next is None: return None prev = None slow_ptr = head fast_ptr = head # Move the fast pointer 2 nodes ahead # and the slow pointer 1 node ahead # until fast pointer reaches end of the list while fast_ptr is not None and fast_ptr.next is not None: fast_ptr = fast_ptr.next.next # Update prev to hold the previous # slow pointer value prev = slow_ptr slow_ptr = slow_ptr.next # At this point slow_ptr points to middle node # Bypass the middle node prev.next = slow_ptr.next # Return the head of the modified list return head def printList(head): temp = head while temp: print(temp.data end=' -> ') temp = temp.next print('NULL') if __name__ == '__main__': # Create a static hardcoded linked list: # 1 -> 2 -> 3 -> 4 -> 5 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) print('Original Linked List: ' end='') printList(head) # Delete the middle node head = deleteMid(head) print('Linked List after deleting the middle node: ' end='') printList(head)
C# 
// C# program to delete middle of a linked list using System; class Node {  public int data;  public Node next;    public Node(int x) {  data = x;  next = null;  } } class GfG {  // Function to delete middle node from linked list  public static Node deleteMid(Node head) {  // If the list is empty return null  if (head == null)  return null;  // If the list has only one node  // delete it and return null  if (head.next == null) {  return null;  }  Node prev = null;  Node slow_ptr = head;  Node fast_ptr = head;  // Move the fast pointer 2 nodes ahead  // and the slow pointer 1 node ahead  // until fast pointer reaches end of the list  while (fast_ptr != null && fast_ptr.next != null) {  fast_ptr = fast_ptr.next.next;  // Update prev to hold the previous   // slow pointer value  prev = slow_ptr;  slow_ptr = slow_ptr.next;  }  // At this point slow_ptr points to middle node  // Bypass the middle node  prev.next = slow_ptr.next;  // Return the head of the modified list  return head;  }  // Function to print the linked list  public static void printList(Node head) {  Node temp = head;  while (temp != null) {  Console.Write(temp.data + ' -> ');  temp = temp.next;  }  Console.WriteLine('NULL');  }  public static void Main(string[] args) {  // Create a static hardcoded linked list:  // 1 -> 2 -> 3 -> 4 -> 5  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  Console.Write('Original Linked List: ');  printList(head);  // Delete the middle node  head = deleteMid(head);  Console.Write  ('Linked List after deleting the middle node: ');  printList(head);  } }
JavaScript 
// javascript program to delete middle of a linked list class Node {  constructor(data)  {  this.data = data;  this.next = null;  } } // Function to delete the middle node from the linked list function deleteMid(head) {  // If the list is empty return null  if (head === null) {  return null;  }  // If the list has only one node delete it and return  // null  if (head.next === null) {  return null;  }  let prev = null;  let slow_ptr = head;  let fast_ptr = head;  // Move the fast pointer 2 nodes ahead  // and the slow pointer 1 node ahead  // until the fast pointer reaches the end of the list  while (fast_ptr !== null && fast_ptr.next !== null) {  fast_ptr = fast_ptr.next.next;  // Update prev to hold the previous slow pointer  // value  prev = slow_ptr;  slow_ptr = slow_ptr.next;  }  // At this point slow_ptr points to the middle node  // Bypass the middle node  prev.next = slow_ptr.next;  // Return the head of the modified list  return head; } function printList(head) {  let temp = head;  while (temp !== null) {  process.stdout.write(temp.data + ' -> ');  temp = temp.next;  }  console.log('null'); } // Create a static hardcoded linked list: // 1 -> 2 -> 3 -> 4 -> 5 let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); process.stdout.write('Original Linked List: '); printList(head); // Delete the middle node head = deleteMid(head); process.stdout.write(  'Linked List after deleting the middle node: '); printList(head);

Çıktı 
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Linked List after deleting the middle node: 1 -> 2 -> 4 -> 5 -> NULL

Zaman karmaşıklığı: Açık). Bağlantılı listenin yalnızca bir geçişi gereklidir
Yardımcı Alan: O (1). Ekstra alana gerek olmadığı için.

İlgili Makale:

  • Bağlantılı listenin ortasını bul