LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists(C语言
题目描述:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例:输入:1->2->4,1->3->4 输出:1->1->2->3->4->4 题目解答:方法1:直接遍历申请头结点,方便在后边插入节点。 运行时间4ms,代码如下。 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1,struct ListNode* l2) { struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* t = head; while(l1 && l2) { if(l1->val > l2->val) { t->next = l2; l2 = l2->next; } else { t->next = l1; l1 = l1->next; } t = t->next; } t->next = (l1 ? l1 : l2); t = head->next; free(head); return t; } 方法2:递归法但递归会用栈空间,如果元素太多,会溢出。 运行时间还4ms,代码如下。 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1,struct ListNode* l2) { if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next,l2); return l1; } else { l2->next = mergeTwoLists(l2->next,l1); return l2; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |