网站短期就业培训班,wordpress 增加侧边栏,南京网站建设方案,江阴市做网站的1.题目 https://leetcode.cn/problems/merge-two-sorted-lists/ 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1#xff1a; 输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]示例 2…1.题目 https://leetcode.cn/problems/merge-two-sorted-lists/ 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]示例 2 输入l1 [], l2 []
输出[]示例 3 输入l1 [], l2 [0]
输出[0]提示 两个链表的节点数目范围是 [0, 50]-100 Node.val 100l1 和 l2 均按 非递减顺序 排列代码模版 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
} 2.自解
一个容易想到的解法:取小的尾插(开一个新的链表)
对于链表list1和list2,可以另外开一个新的链表,再将list1和list2的val复制进新链表的节点,最后返回新链表的头结点的地址即可
不加思索写出以下代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1list1;struct ListNode* cur2list2;if (list1NULL)return list2;if (list2NULL)return list1;struct newListNode{int new_val;struct ListNode* new_next;};struct newListNode* new_nextNULL;struct newListNode* newheadNULL;struct newListNode* m_m_new(struct newListNode*)malloc(sizeof(struct newListNode));newheadm_m_new;newhead-new_nextNULL;struct newListNode* new_curnewhead;while(cur1!NULL cur2!NULL){if (cur1NULL){new_cur-new_valcur2-val;cur2cur2-next;//分配新结点的空间struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;continue;}if (cur2NULL){new_cur-new_valcur1-val;cur1cur1-next;struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;continue;}if (cur1-valcur2-val){new_cur-new_valcur1-val;cur1cur1-next;struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;}else{new_cur-new_valcur2-val;cur2cur2-next;//分配新结点的空间struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;}}new_cur-new_nextNULL;new_curNULL;return newhead;
}
运行时出现问题 发现while循环的条件写错了!!
应该改成
while(!(cur1NULL cur2NULL))
完整代码
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1list1;struct ListNode* cur2list2;if (list1NULL)return list2;if (list2NULL)return list1;struct newListNode{int new_val;struct ListNode* new_next;};struct newListNode* new_nextNULL;struct newListNode* newheadNULL;struct newListNode* m_m_new(struct newListNode*)malloc(sizeof(struct newListNode));newheadm_m_new;newhead-new_nextNULL;struct newListNode* new_curnewhead;struct newListNode* before_new_curNULL;while(!(cur1NULL cur2NULL)){if (cur1NULL){new_cur-new_valcur2-val;cur2cur2-next;struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;before_new_curnew_cur;new_curm_new;new_cur-new_nextNULL;continue;}if (cur2NULL){new_cur-new_valcur1-val;cur1cur1-next;struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;before_new_curnew_cur;new_curm_new;continue;}if (cur1-valcur2-val){new_cur-new_valcur1-val;cur1cur1-next;struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;}else{new_cur-new_valcur2-val;cur2cur2-next; struct newListNode* m_new(struct newListNode*)malloc(sizeof(struct newListNode));new_cur-new_nextm_new;new_curm_new;}}before_new_cur-new_nextNULL;return newhead;
}
before_new_cur是当cur1NULL或cur2NULL,备份new_cur的前一个节点的地址
提交结果 3.其他解法
方法1:取小的尾插(不开新链表)
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* cur1list1;struct ListNode* cur2list2;struct ListNode* headNULL;struct ListNode* tailNULL;if (list1NULL)return list2;if (list2NULL)return list1;while (cur1 cur2){if (cur1-valcur2-val){if (headNULL){headtailcur1;}else{tail-nextcur1;tailtail-next;}cur1cur1-next;}else{if (headNULL){headtailcur2;}else{tail-nextcur2;tailtail-next;}cur2cur2-next; }}if(cur1)tail-nextcur1;if(cur2)tail-nextcur2;return head;
}
分析
尾插要有尾指针tail(这样不用频繁找尾),同时要有指向头节点的指针head用于返回
cur1-valcur2-val和cur1-valcur2-val操作方式是类似的
