LeetCode 【21. Merge Two Sorted Lists】

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思路.首先判断是否有空链表，如果有，则直接返回另一个链表，如果没有，则开始比较两个链表的当前节点，返回较小的元素作为前驱，并且指针向后移动一位，再进行比较，如此循环，知道一个链表的next指向NULL，将另一个链表的后序元素进行连接即可。

迭代：

/**

 * 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 == 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(l2->next, l1);

            return l2;

        }

    }

};

循环：

/**

 * 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==NULL ) return l2;

        if( l2==NULL ) return l1;

        ListNode* head = (l1->val > l2->val)?l2:l1;

        ListNode* temp;

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

        {

            while(l1->next!=NULL&&l2!= NULL &&l1->next->val <= l2->val)

            {

                l1 = l1->next;

            }

            if(l1 != NULL&&l2 !=NULL &&l1->val <= l2->val)

            {

                temp = l1->next;

                l1->next = l2;

                l1 = temp;

            }

            while(l2->next !=NULL&& l1 !=NULL &&l2->next->val <= l1->val)

            {

                l2 = l2->next;

            }

             if(l2 != NULL &&l1 != NULL&&l2->val <= l1->val)

            {

                temp = l2->next;

                l2->next = l1;

                l2 = temp;

            }

        }

        return head;

    }

};

巴特西

LeetCode 【21. Merge Two Sorted Lists】

最新文章

热门文章