首页 > 代码库 > LeetCode Merge Two Sorted Lists 归并排序

LeetCode Merge Two Sorted Lists 归并排序

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {12         if(l1==0)    return l2;13         if(l2==0)    return l1;14         ListNode *start=0,*end=0;15         if(l1->val<l2->val){16             start=end=l1;17             l1=l1->next;18         }19         else{20             start=end=l2;21             l2=l2->next;22         }23         while(l1!=0&&l2!=0){24             if(l1->val<l2->val){25                 end->next=l1;26                 l1=l1->next;27             }28             else{29                 end->next=l2;30                 l2=l2->next;31             }32             end=end->next;33         }34         if(l1==0)35             end->next=l2;36         else37             end->next=l1;38         return start;   39     }40 };

题意:将两个已有序的链表归并为一个有序的链表,并返回。

思路:就不用递归!第一个值先比较大小,将start指向小的那个,作为最后的返回地址。li不断和l2比较,每比较一次就将一个结点归到end指针的后面,end也是从start开始的。最后一定会将两个链表串在一起,并有序。比喻:两个手分别拿着已有序的扑克牌,每次挑出手中最小的点数,放在桌子上,最后他们就从下到上有序地叠在一起了。那么一只手先放光了,那么就可以把剩余的牌直接放桌子上了。

 

LeetCode Merge Two Sorted Lists 归并排序