--每周分享--

分享内容：

1.单链表的归并排序

2.一道有趣的思考题

分享细节：

单链表的归并排序

主要思想：递归

怎么理解？下面具体说明：

1.首先，我从整体的思考步骤说明：先分区，再排序，最后合并

2.理解递归：递归什么？怎么递归？递归结束条件是什么？递归的返回值是什么？

递归什么：我们想要通过找中间值来不断的分割链表，既然需要不断地分割，那么就需要递归本身区找中间值分割链表。由于我们最初说“先分区，再排序，最后合并”，那么分区操作就得写在前面。

怎么递归：找到中间值，有两段链表，那么就需要调用两次函数，分别对两边的链表继续分割。这就要提到一个注意点：怎么断开？如果在数组中，我们直接就用索引，【左边，mid】【mid + 1，右边】，但是在链表中我们要让mid->next = NULL,让链表在mid处断开，因为：确保每个递归步骤都在将链表分割为较小的部分时维护链表的正确性。在递归过程中，排序的过程可能会受到影响，因为递归过程中会改变链表的连接关系。

递归结束条件是什么：分为一个结点时结束递归，开始合并。

递归的返回值就是合并后返回的链表头。

那么，其实从递归结束条件就可以知道：“分为一个结点时结束递归，开始合并。”，那么压根就不需要排序，为什么？因为每个结点已经成为一个结点了，其实就是一个个的有序链表。

上代码看一下：

Node* merge(Node* head1, Node* head2) {
	if (head1 == NULL) {
		return head2;
	}

	if (head2 == NULL) {
		return head1;
	}
	if (head1->data < head2->data) {
		head1->next = merge(head1->next, head2);
		return head1;
	}

	else {
		head2->next = merge(head1, head2->next);
		return head2;
	}

}

Node* rank_kuai(Node* head){
	if (head == NULL || head->next == NULL) {
		return head;
	}

	Node* low = head;
	Node* kuai = head->next;
	 Node* mid = NULL;
	 Node* mid_next = NULL;
	while (kuai != NULL && kuai->next != NULL) {
		low = low->next;
		kuai = kuai->next->next;
	}
	mid = low;
	mid_next = mid->next;
	mid->next = NULL;
	head = rank_kuai(head);
	mid_next = rank_kuai(mid_next);
	return merge(head,mid_next);

}

一道有趣的思考题

爬楼梯：

 可以大胆的想一想：（贪心）

我们想：上第n阶台阶其实就是第n-1阶台阶的上法 + 第n-2阶台阶的上法

怎么理解：其实很简单：第n-1阶台阶到最后一阶台阶和第n-2阶台阶到最后一阶台阶的最后一步不一样，那么他们之前所有的走法都不可能重复，所以直接相加即可。

那么，此时就是一道斐波那契数列的应用问题。

代码：

int climbStairs(int n) {
//贪心：
    //斐波那契数列的应用
    if(n == 1){
        return 1;
    }
    if(n == 2){
        return 2;
    }
    
    int f1 = 1,f2 = 2;
    int f3 = f1 + f2;
    while(n>3){
        f1 = f2;
        f2 = f3;
        f3 = f1 + f2;
        n--;
    }
    
    return f3;
}