一、前记(3/3)

怎么感觉现在都顺延了一天,不行不能如此懒惰,这个星期必然打满卡。今天没有使用Python来写题,因为今天的题目是我结合考研专业课复习来选择的题目。用C语言写的,还是比较有意思。

二、题目描述

这个题是一个典型的单链表插入重组的一个问题。只要是链表的位置移动都还是比较简单的,只需要把地址赋值一下就可以了。

三、解题思路

1、我的思路

我的思路简简单单,普普通通。重新开辟一块新的单链表内存空间(t=head),大小就为struct ListNode就行,作用是用于记录;然后比较两个单链表里面的值,让t->next指向较小值,然后较小值的单链表指向下一个值;如果出现某一链表有剩余,那么将剩余的地址放到新的单链表里面就行

参考代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {	//指针类型全为结构体类型
	if (!l1)	//如果l1不存在,直接返回l2
		return l2;
	if (!l2)	//如果l2不存在,直接返回l1
		return l1;

	struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)), *t = head;	//新开辟内存空间
	while (l1 && l2) {	//l1和l2都存在的时候就不断的进行比较
		if (l1->val < l2->val) {	//l1和l2的val进行比较,选出值小的
			t->next = l1;	//新开辟的内存地址的指针域指向l1(这里是地址)
			l1 = l1->next;	//将l1上的指针挪动一位
		}
		else {
			t->next = l2;
			l2 = l2->next;
		}
		t = t->next;	//新开辟的单链表的指针也要移动一位
	}
	if (l1)      t->next = l1;	//l1剩余的直接放到最末尾
	else if (l2) t->next = l2;
	return head->next;	//返回的是结构体指针新开辟单链表的头结点的指针域
}

2、别人的思路

别人的思路里面有一个递归思想还是挺有意思的

if (!l1)
		return l2;
	if (!l2)
		return l1;
	if (l1->val < l2->val){
		l1->next = mergeTwoLists(l1->next, l2);
		return l1;
	}
	else{
		l2->next = mergeTwoLists(l1, l2->next);
		return l2;
	}

四、学到了什么?

1、单链表里面的地址赋值操作

2、单链表里面的递归操作