Leecode之合并两个有序链表

一.题目及剖析

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;}
}