<commit_before>\chapter{排序}

\section{Merge Sorted Array} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-sorted-array}


\subsubsection{描述}
Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
//LeetCode, Merge Sorted Array
// 时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int ia = m - 1, ib = n - 1, icur = m + n - 1;
        while(ia >= 0 && ib >= 0) {
            A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
        }
        while(ib >= 0) {
            A[icur--] = B[ib--];
        }
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Merge Two Sorted Lists，见 \S \ref{sec:merge-two-sorted-lists}
\item Merge k Sorted Lists，见 \S \ref{sec:merge-k-sorted-lists}
\myenddot


\section{Merge Two Sorted Lists} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-two-sorted-lists}


\subsubsection{描述}
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.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
//LeetCode, Merge Two Sorted Lists
// 时间复杂度O(min(m,n))，空间复杂度O(1)
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        ListNode h(-1);
        ListNode *p = &h;
        for (; l1 != nullptr && l2 != nullptr; p = p->next) {
            if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
            else { p->next = l1; l1 = l1->next; }
        }
        p->next = l1 != nullptr ? l1 : l2;
        return h.next;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Merge Sorted Array \S \ref{sec:merge-sorted-array}
\item Merge k Sorted Lists，见 \S \ref{sec:merge-k-sorted-lists}
\myenddot


\section{Merge k Sorted Lists} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-k-sorted-lists}


\subsubsection{描述}
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.


\subsubsection{分析}
可以复用Merge Two Sorted Lists（见 \S \ref{sec:merge-two-sorted-lists}）的函数


\subsubsection{代码}<commit_msg>change variable name h to dummy to follow name convention<commit_after>\chapter{排序}

\section{Merge Sorted Array} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-sorted-array}


\subsubsection{描述}
Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
//LeetCode, Merge Sorted Array
// 时间复杂度O(m+n)，空间复杂度O(1)
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int ia = m - 1, ib = n - 1, icur = m + n - 1;
        while(ia >= 0 && ib >= 0) {
            A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
        }
        while(ib >= 0) {
            A[icur--] = B[ib--];
        }
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Merge Two Sorted Lists，见 \S \ref{sec:merge-two-sorted-lists}
\item Merge k Sorted Lists，见 \S \ref{sec:merge-k-sorted-lists}
\myenddot


\section{Merge Two Sorted Lists} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-two-sorted-lists}


\subsubsection{描述}
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.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
//LeetCode, Merge Two Sorted Lists
// 时间复杂度O(min(m,n))，空间复杂度O(1)
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        ListNode dummy(-1);
        ListNode *p = &dummy;
        for (; l1 != nullptr && l2 != nullptr; p = p->next) {
            if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
            else { p->next = l1; l1 = l1->next; }
        }
        p->next = l1 != nullptr ? l1 : l2;
        return dummy.next;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Merge Sorted Array \S \ref{sec:merge-sorted-array}
\item Merge k Sorted Lists，见 \S \ref{sec:merge-k-sorted-lists}
\myenddot


\section{Merge k Sorted Lists} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:merge-k-sorted-lists}


\subsubsection{描述}
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.


\subsubsection{分析}
可以复用Merge Two Sorted Lists（见 \S \ref{sec:merge-two-sorted-lists}）的函数


\subsubsection{代码}
{'fraction_non_alphanumeric': 0.17219655606887863, 'fraction_numerical': 0.011759764804703907, 'mean_word_length': 2.897708674304419, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6157155', 'n_tokens_mistral': 1808, 'n_tokens_neox': 1842, 'n_words': 518}