一.题目及剖析
https://leetcode.cn/problems/merge-two-sorted-lists/description/
二.思路引入
用指针遍历两个链表并实时比较,较小的元素进行尾插,然后较小元素的指针接着向后遍历
三.代码引入
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode *newHead, *newTail, *l1, *l2; newHead = newTail = (struct ListNode*)malloc(sizeof(struct ListNode)); l1 = list1; l2 = list2; if(list1 == NULL) return list2; if(list2 == NULL) return list1; while(l1 && l2) { if(l1->val > l2->val) { newTail->next = l2; newTail = newTail->next; l2 = l2->next; } else { newTail->next = l1; newTail = newTail->next; l1 = l1->next; } } if(l1) newTail->next = l1; if(l2) newTail->next = l2; return newHead->next; }
四.扩展
当然,这道题的思路并不止一种,这种思路是一般方法,我们还可以用递归去写
/** * 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(l1,l2->next); return l2; } }
