[Leetcode] 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.

题意：合并两个排好的链表并返回新的链表。

可以使用归并排序，从两链表的表头，取出结点，比较两值，将较小的放在新链表中。如1->3->5->6和2->4->7->8，先将1放入新链表，然后将3和2比较，较小值放入新链表中，从1到3只要pre=pre->next即可。当其中有一条链表被访问完，结束循环，找出该链表，将其接在新链表的后面即可。

/**

 * 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)

    {

        ListNode *newList=new ListNode(-);

        ListNode *pre=newList;

        while(l1&&l2)

        {

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

            {

                pre->next=l2;

                l2=l2->next;

            }

            else

            {

                pre->next=l1;

                l1=l1->next;

            }

            pre=pre->next;

        }

        if(l1)

            pre->next=l1;

        else

            pre->next=l2;

        return newList->next;

    }

};

巴特西

[Leetcode] Merge two sorted lists 合并两已排序的链表

最新文章

热门文章