Obstructive sleep apnea (OSA) is a popular sleep disorder. Traditional OSA diagnosis methods are cumbersome and expensive, which bring inconvenience for patient diagnosis and heavy workload for physician. Automatically identifying OSA patients from electrocardiogram (ECG) records is important for clinical diagnosis and treatment. In this paper, a new method based on the frequency and network domains is proposed to automatically recognize OSA patients with nocturnal ECG records. First, each RR-interval (beat to beat heart rate) series was divided into segments. By calculating the power spectral density (PSD) of heart rate variability segment with Lomb-Scargle method, the dynamic time warping (DTW) distance was used to evaluate the similarity (dissimilarity) of the lower frequency in the PSD series, then the DTW distance matrix was transformed to a binary matrix, and then network metrics were calculated to discriminate OSA patients with healthy subjects. The new method was tested with data of 389 subjects collected from two public databases that consist of normal subjects without OSA (apnea-hypopnea index, AHI 5) and OSA patients (AHI 5). Results show that a single network metric (local clustering coefficient) can recognize OSA patients with 90.1% accuracy, 88.29% sensitivity, and 90.5% specificity, and confirm the potential of using the ECG records for OSA patients recognition.