LeetCode Merge Two Sorted Lists 归并排序

题意：

　　将两个有序的链表归并为一个有序的链表。

思路：

　　设合并后的链表为head，现每次要往head中加入一个元素，该元素要么属于L1，要么属于L2，可想而知，此元素只能是L1或者L2的首个元素，那么进行一次比较就可以知道是谁了。操作到L1或L2其中一个已经没有元素为止，剩下的直接加到head后面。

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

         if(l1==)    return l2;

         if(l2==)    return l1;

         ListNode *start=,*end=;

         if(l1->val<l2->val){

             start=end=l1;

             l1=l1->next;

         }

         else{

             start=end=l2;

             l2=l2->next;

         }

         while(l1!=&&l2!=){

             if(l1->val<l2->val){

                 end->next=l1;

                 l1=l1->next;

             }

             else{

                 end->next=l2;

                 l2=l2->next;

             }

             end=end->next;

         }

         if(l1==)

             end->next=l2;

         else

             end->next=l1;

         return start;

     }

 };

AC代码

python3

 # Definition for singly-linked list.

 # class ListNode(object):

 #     def __init__(self, x):

 #         self.val = x

 #         self.next = None

 class Solution(object):

     def mergeTwoLists(self, l1, l2):

         """

         :type l1: ListNode

         :type l2: ListNode

         :rtype: ListNode

         """

         head=cur=ListNode(0)

         while l1 and l2:

             if l1.val<l2.val:    cur.next, l1=l1, l1.next

             else:                cur.next, l2=l2, l2.next

             cur=cur.next

         if l1:    cur.next=l1

         if l2:    cur.next=l2

         return head.next

AC代码

巴特西

LeetCode Merge Two Sorted Lists 归并排序

最新文章

热门文章