By

文章目录
  1. 1. Merge Two Sorted Lists
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

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.

思路

类似于归并排序中的归并

解题

c++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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 dummy(-1);
        ListNode *cur=&dummy;
        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 dummy.next;
    }
};

Python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param {ListNode} l1
    # @param {ListNode} l2
    # @return {ListNode}
    def mergeTwoLists(self, l1, l2):
        dummy=ListNode(0)
        cur=dummy
        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 dummy.next
leetcode
leetcode,linkList
文章目录
  1. 1. Merge Two Sorted Lists
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题