C++ and Dart Solutions for Deleting the Middle Node of a Linked List

C++ and Dart Solutions for Deleting the Middle Node of a Linked List

This article presents C++ and Dart implementations for deleting the middle node of a linked list. The solutions leverage a fast and slow pointer technique to efficiently locate and remove the target node.

C++ Implementation

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;  // 头节点为空或只有一个节点时返回空指针
        }
        
        ListNode* p = head;
        ListNode* q = head;
        ListNode* prev = nullptr;
        
        while (q != nullptr && q->next != nullptr) {
            prev = p;
            p = p->next;
            q = q->next->next;
        }
        
        if (prev != nullptr) {
            prev->next = p->next;
        } else {
            head = head->next;  // 头节点为要删除的节点时更新头节点
        }
        
        delete p;
        
        return head;
    }
};

Dart Implementation

class Solution {
  ListNode deleteMiddle(ListNode head) {
    if (head == null || head.next == null) {
      return null;  // 头节点为空或只有一个节点时返回空指针
    }

    ListNode p = head;
    ListNode q = head;
    ListNode prev = null;

    while (q != null && q.next != null) {
      prev = p;
      p = p.next;
      q = q.next.next;
    }

    if (prev != null) {
      prev.next = p.next;
    } else {
      head = head.next;  // 头节点为要删除的节点时更新头节点
    }

    p = null;

    return head;
  }
}

Explanation

1. Initialization: The code starts by initializing three pointers: p, q, and prev. p is the slow pointer, q is the fast pointer, and prev points to the node before p.
2. Fast and Slow Pointers: The while loop moves q two steps at a time, while p moves one step at a time. This ensures that when q reaches the end of the list, p will be pointing to the middle node.
3. Deletion: After the loop completes, p will be pointing to the middle node. The code then checks if prev is not null (meaning the middle node is not the head). If so, it updates prev's next pointer to skip over p, effectively deleting it. If prev is null, the head node is the middle node, and we update the head pointer to its next node.
4. Cleanup: Finally, p is set to null to break any potential circular references. The function returns the updated head pointer.

Conclusion

This article presented C++ and Dart implementations for deleting the middle node of a linked list. The solutions demonstrate the effectiveness of the fast and slow pointer technique in efficiently navigating and manipulating linked lists. By understanding these implementations, you can effectively delete middle nodes from linked lists in your own code.