Long non-coding RNAs (lncRNAs) play important roles in diagnosis and prognosis of human cancers. With the development of microarray and RNA-seq, gene expression were measured in more and more tumor types for identification of prognostic markers. However, lncRNA expression profiles of tumor patients with follow-up information were rare. In this study, we developed a novel simple computational approach, which didn't use lncRNA expression, to identify lncRNAs associated with the survival of melanoma patients through integrating gene expression and lncRNA-target networks. First, we calculated the significance of associations between gene expression and patients' survival. Second, we constructed the experimentally validated lncRNA-target gene networks. Next, the significance of lncRNAs were obtained by combination of the p-values of their neighbor genes. Finally, we identified 15 lncRNAs that were significantly associated with the survival of melanoma patients (p<0.05), which were supported by functional analysis and literature review. Collectively, this study provides an effective approach to predict the lncRNA signatures for outcomes of tumor patients without lncRNA expression profiles.