leetcode21.合并两个有序链表

目录 问题描述示例提示 具体思路思路一 代码实现

问题描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

题目链接：合并两个有序链表

示例

提示

  两个链表的节点数目范围是 [0, 50]   -100 <= Node.val <= 100   l1 和 l2 均按 非递减顺序 排列

具体思路 思路一

  遍历两个链表，取小的进行尾插就行，当list1先结束的时候，直接将list2进行尾插，否则直接将list1进行尾插

代码实现 //思路1 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 == NULL) return list2; if(list2 == NULL) return list1; struct ListNode* head=NULL; struct ListNode* tail=NULL; while(list1&&list2) { if(list1->val<list2->val) { if(tail== NULL) { head=tail=list1; } else { tail->next=list1; tail=tail->next; } list1=list1->next; } else{ if(tail== NULL) { head=tail=list2; } else { tail->next=list2; tail=tail->next; } list2=list2->next; } } if(list1) { tail->next=list1; } if(list2) { tail->next=list2; } return head; }