Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
剑指Offer68 / # 01 - 25
|剑指Offer01 - 25

01 - 25

3.数组中重复的数字

  • 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

  • 输入：
    [2, 3, 1, 0, 2, 5, 3]
    输出：2 或 3

  • 方法：

  1. 哈希表
  2. sort后，进行查找
  3. 元素交换到其下标对应位置（最优解）
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
int findRepeatNumber(vector<int>& nums) {
	//对时间和空间的要求

	//1.哈希表  空间On，时间0n
	// int len = nums.size();
	// if(len<=1)return 0;
	// unordered_map<int,int>arr;
	// for(int i = 0;i<len;i++){
	//     if(++arr[nums[i]] > 1){
	//         return nums[i];
	//     }    
	// }
	// return 0;

	//2.空间对元素进行排序，然后相邻元素是否重复 空间O（1），时间0（n*logn）
	//sort(nums.begin(),nums.end());

	//3.空间O（1），时间0（n）/ 把元素换到对应的下标
	for (int i = 0; i < nums.size(); i++) {
		if (nums[i] != i) {
			if (nums[i] == nums[nums[i]])
				return nums[i];
			else {
				int temp = nums[i];
				nums[i] = nums[temp];
				nums[temp] = temp;
			}
		}
	}
	return -1;
}

4.二维数组中的查找

  • 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

  • 输入：

  • [

  • [1, 4, 7, 11, 15],

  • [2, 5, 8, 12, 19],

  • [3, 6, 9, 16, 22],

  • [10, 13, 14, 17, 24],

  • [18, 21, 23, 26, 30]

  • ]

  • 给定 target = 5，返回 true。

  • 给定 target = 20，返回 false。

  • 方法：

  • 特征：矩阵，从左至右，从上至下依次递增
  • 使用：线性查找，从有右上角开始查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
	if (matrix.size() == 0)
		return false;
	//线性查找
	//从右上角开始走，往左变小，往下变大
	int m = matrix.size();
	int n = matrix[0].size();
	int row = 0;
	int col = n - 1;
	while (row < m && col >= 0) {
		if (matrix[row][col] == target)
			return true;
		else if (matrix[row][col] > target)
			col--;
		else
			row++;
	}
	return false;
}

5.替换空格

  • 请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

  • 输入：

输入：s = “We are happy.”

输出：”We%20are%20happy.”

  • 方法：

  1. 新的string，遍历后增加替换
  2. string的成员函数replace，A.replace(i_开始的下标 , len_长度 , “替换的字符”)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string replaceSpace(string s) {
	//需要而外开销
	// string ans;
	// for(int i = 0; i<s.size(); i++) {
	//     if(s[i] == ' ') 
	//         ans += "%20" ;
	//     else    
	//         ans += s[i];
	// }
	// return ans;
	//不需要而外开销
	if (s.size() == 0) return s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ' ')
			s.replace(i, 1, "%20");//s.replace(开始下标，结束下标，替换元素)
	}
	return s;
}

6.从头到尾打印链表

  • 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

  • 输入：

  • 输入：head = [1,3,2]

  • 输出：[2,3,1]

  • 方法：

  1. 利用deque
  2. 利用vector（倒置初始化）/ reserve
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> reversePrint(ListNode* head) {
	// deque<int> deq;

	//  while(head!=NULL){
	//      deq.push_front(head->val);
	//      head = head->next;
	//  }
	// vector<int>arr(deq.begin(),deq.end());
	vector<int> deq;
	while (head != NULL) {
		deq.push_back(head->val);
		head = head->next;
	}
	vector<int>arr(deq.rbegin(), deq.rend());

	return arr;
}

7. 重建二叉树

  • 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

  • 输入：

  • 前序遍历 preorder = [3,9,20,15,7]

  • 中序遍历 inorder = [9,3,15,20,7]

  • 方法：

  • 反复利用数组的下标初始化

  • 先序——定根

  • 中序——定区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	return build(preorder, inorder, 0, 0, preorder.size() - 1);
}                          //前序数组、中序数组、前序根节点位置、中序划分区间、中序划分区间
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int root, int start, int end) {
	if (start > end)
		return NULL;
	//先序定根
	TreeNode* tree = new TreeNode(preorder[root]);
	
   //中序定两侧子树
	//定位根节点在中序的位置
	int i = start;
	while (i < end &&preorder[root] != inorder[i])
		i++;
					//根据前序—根	    //根据中序—区间
	tree->left = build(preorder, inorder, root + 1, 	start, i - 1);
	tree->right = build(preorder, inorder, root + 1 + i - start, i + 1,  end);
	return tree;
}

9.用两个栈实现队列

  • 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

  • 输入：略

  • 方法：

  1. 利用两个栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
stack<int>s1;
stack<int>s2;
//利用两个栈，加的时候，先将s1的放入s2, 然会加s1，s2的再回来
void appendTail(int value) {
	while (!s1.empty()) {
		int temp = s1.top();
		s2.push(temp);
		s1.pop();
	}
	s1.push(value);
	while (!s2.empty()) {
		int temp = s2.top();
		s1.push(temp);
		s2.pop();
	}
}
int deleteHead() {
	if (s1.empty())
		return -1;
	int temp = s1.top();
	s1.pop();
	return temp;
}

10-1.斐波那契数列

  • 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

  • 输入：

输入：n = 2
输出：1

输入：n = 5
输出：5

  • 方法：

  1. dp方程
  2. a = a + b、b = a - b
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
int fib(int n) {
	//第一种
	// if(n==0)return 0;                
	// if(n<=2)return 1;

	// vector<int>dp(n+1,0);
	// dp[0] = 0;
	// dp[1] = 1;
	// for(int i =2;i<n+1;i++){
	//     dp[i] = (dp[i-1]+dp[i-2])%1000000007;
	// }
	// return dp[n];

	//第二种
	if (n == 0)return 0;
	if (n <= 2)return 1;

	int a = 1;
	int b = 0;
	for (int i = 2; i <= n; i++) {
		a = a + b;
		b = a - b;//b存储前一个数的值
		a %= 1000000007;
	}
	return a;
}

10-2 .青蛙跳台阶问题

  • 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

  • 同上

11. 旋转数组的最小数字

  • 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

  • 输入：

  • 输入：[3,4,5,1,2]

  • 输出：1

  • 输入：[2,2,2,0,1]

  • 输出：0

  • 解：就是找到最小的那个数，就是导致数组旋转

  • 方法：

  1. 二分法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int minArray(vector<int>& numbers) {
	//二分查找
	if (numbers.size() == 1)return numbers[0];
	int L = 0, R = numbers.size() - 1;
	while (L < R) {
		//寻找最小的数在哪个区间，再加以考虑
		int mid = (L + R) / 2;
		if (numbers[mid] < numbers[R]) {  
			R = mid;
		}
		else if (numbers[mid] > numbers[R]) {
			L = mid + 1;
		}
		else
			R--;
	}
	return numbers[L];
}

12.矩阵中的路径

  • 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

  • 输入：

  • [[“a”,“b”,”c”,”e”],
  • [“s”,“f”,“c”,”s”],
  • [“a”,”d”,“e”,”e”]]
  • “bfce” ，true

  • 方法：

  • 遍历数组
  • 回溯，辅助数组vis，dfs
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
bool exist(vector<vector<char>>& board, string word) {
	int len = board.size();
	if (len == 0 || board[0].size() == 0 || word.empty())return false;
	vector<vector<bool>>vis(len, vector<bool>(board[0].size(), true));//辅助数组
	for (int i = 0; i < board.size(); i++) {
		for (int j = 0; j < board[0].size(); j++) {
			if (board[i][j] == word[0]) {
				if (dfs(i, j, board, word, 0, vis))
					return true;
			}
		}
	}
	return false;
}
bool dfs(int i, int j, vector<vector<char>>& board, string word, int length, vector<vector<bool>>&vis) {
	//回溯的返回条件
	if (length == word.size())
		return true;
	//排除不合法
	if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || vis[i][j] == false || board[i][j] != word[length])
		return false;

	//做出选择
	vis[i][j] = false;
	//回溯函数，有真则真
	bool res = dfs(i, j + 1, board, word, length + 1, vis) || dfs(i, j - 1, board, word, length + 1, vis) ||
		dfs(i + 1, j, board, word, length + 1, vis) || dfs(i - 1, j, board, word, length + 1, vis);
	//撤销选择
	vis[i][j] = true;
	return res;
}

13. 机器人的运动范围

  • 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

  • 输入：
    输入：m = 2, n = 3, k = 1
    输出：3

输入：m = 3, n = 1, k = 0
输出：1

  • 方法：

  1. 典型的BFS，但是只有两个方向需要注意
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
32
33
34
35
36
37
38
int get(int x) {
	int res = 0;
	while (x) {
		res += x % 10;
		x /= 10;
	}
	return res;
}

int movingCount(int m, int n, int k) {
	if (!k) return 1;

	vector<vector<int>>vis(m, vector<int>(n, 0));
	vis[0][0] = 1;

	queue<pair<int, int>> Q;
	Q.push(make_pair(0, 0));

	int dx[2] = { 0, 1 };
	int dy[2] = { 1, 0 };

	int ans = 1;
	while (!Q.empty()) {
		auto[x, y] = Q.front();
		Q.pop();
		for (int i = 0; i < 2; ++i) {
			int tx = dx[i] + x;
			int ty = dy[i] + y;
			if (tx >= 0 && tx < m && ty >= 0 && ty < n &&
				get(tx) + get(ty) < k + 1 && vis[tx][ty] == 0) {
				Q.push(make_pair(tx, ty));
				vis[tx][ty] = 1;
				ans++;
			}
		}
	}
	return ans;
}

14-1.剪绳子

  • 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

  • 输入：
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

  • 解：只有绳子大于4的时候，才需要剪开可以乘积变大

    • 1 / 1 0
    • 2 / 1*1=1
    • 3 / 1*2=2
    • 4 / 2*2=4
    • 5 / 2*3=5 //开始变化

  • 方法：

  1. 找规律
  2. dp动态规划
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
int cuttingRope(int n) {
	//1.贪心算法，找规律，拆分成3的倍数乘积是最大的
	// if (n < 4)return n - 1;
	// int a = n / 3, b = n % 3;
	// if (b == 0)return a = pow(3, a);
	// if (b == 1)return a = pow(3, a-1) * 4;
	// if (b == 2)return a = pow(3, a) * 2;
	// return a;

	//2.动态规划
	//只有大于4的绳子才有分的必要 ，4分成2*2没有变化，5分成2*3可以变大
	if (n < 4)return n - 1;
	if (n == 4)return 4;
	vector<int> dp(n + 1);
	dp[1] = 1;//绳长度为1的最大乘积
	dp[2] = 2;//绳长度为2的最大乘积
	dp[3] = 3;//绳长度为3的最大乘积
	dp[4] = 4;//绳长度为4的最大乘积
	for (int i = 5; i <= n; i++) {
		int maxNum = 0;
		for (int j = 1; j <= i / 2; j++) {
			maxNum = max(maxNum, dp[i - j] * dp[j]);
		}
		dp[i] = maxNum;
	}
	return dp[n];
}

14-2.剪绳子 II

  • 同上

15.二进制中1的个数

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
	int res = 0;
	while (n) {
		if (n & 1)
			res++;
		n = n >> 1;
	}
	return res;
}

16.数值的整数次方

  • 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

  • 输入：

输入: 2.00000, 10
输出: 1024.00000

输入: 2.10000, 3
输出: 9.26100

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

  • 方法：

  1. dfs————拆分拆分 / 化繁为简
1
2
3
4
5
6
7
8
9
double myPow(double x, int n) {
	if (n == 0) return 1;
	if (n == 1) return x;
	if (n == -1) return 1 / x;
	double half = myPow(x, n / 2);
	double add = myPow(x, n % 2);

	return half * half*add;
}

17.打印从1到最大的n位数

  • 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

  • 输入：
    输入: n = 1
    输出: [1,2,3,4,5,6,7,8,9]

  • 主要考大数问题，用字符串模拟加法 到了这，这题变得毫无意义

  • 方法：

    • 字符串解决大数问题 
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
vector<int> res;
vector<int> printNumbers(int n) {
	if (n <= 0) return res;
	string number(n, '0');
	for (int i = 0; i <= 9; i++) {
		number[0] = i + '0';
		permutionNum(number, n, 1);
	}
	return res;
}
void permutionNum(string &number, int length, int index) {
	if (index == length) {
		saveNum(number);
		return;
	}
	else {
		for (int i = 0; i < 10; i++)
		{
			number[index] = '0' + i;
			permutionNum(number, length, index + 1);
		}
	}
}
void saveNum(string number) {
	string tempStr(number.size(), '0');
	std::cout << stoi(number) << " ";
	if (number != tempStr)
		res.push_back(stoi(number));
}
/////////////////////////////////////////////////////////
void bigAdd(string num1, string num2, string &res) {
	int carry = 0;
	int len1 = num1.length() - 1;
	int len2 = num2.length() - 1;
	res = "";
	while (len1 >= 0 || len2 >= 0) {
		int a = len1 >= 0 ? num1[len1--] - '0' : 0;//从最后一位开始相加，不够的补0
		int b = len2 >= 0 ? num2[len2--] - '0' : 0;
		int tmp = a + b + carry;
		carry = tmp / 10;//进位
		res = to_string(long long(tmp % 10)) + res;
	}
	if (carry) {//如果最高位有进位，加上
		res = to_string(long long(carry)) + res;
	}
}

18.删除链表的节点

  • 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

  • 输入：

  • 输入: head = [4,5,1,9], val = 5

  • 输出: [4,1,9]

  • 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

  • 输入: head = [4,5,1,9], val = 1

  • 输出: [4,5,9]

  • 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

  • 方法：

  1. 原题剑指1：给定头节点和要删除的节点（快速删除）

    • 删除要删除节点的下一个节点，将下一个节点的值赋给前一个结点
    • 当最后一个节点为空，还是需要从头遍历

  2. 原题剑指2：删除链表中的重复节点

    • 使用两个辅助指针实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* deleteNode(ListNode* head, int val) {
	if (head == NULL)
		return head;
	if (head->val == val)
		return head->next;

	//保存头节点
	ListNode* pre = head;
	//开始
	ListNode* temp = NULL;
	while (head->next && head) {
		temp = head;
		head = head->next;
		if (head->val == val) {
			temp->next = head->next;
			break;
		}
	}
	return pre;
}

19. 正则表达式匹配

  • 请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

  • 输入:

  • s = “aa”

  • p = “a”

  • 输出: false

  • 解释: “a” 无法匹配 “aa” 整个字符串。

  • 输入:

  • s = “aa”

  • p = “a*”

  • 输出: true

  • 解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

  • 方法：

1
2
3
4
5
6
7
8
9
10
bool isMatch(string s, string p) {
	if (p.empty()) return s.empty();
	if (p[1] == '*') {
		return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.'))
			&& isMatch(s.substr(1), p);
	}
	else {
		return !s.empty() && (s[0] == p[0] || p[0] == '.') && (isMatch(s.substr(1), p.substr(1)));
	}
}

20.表示数值的字符串

  • 输入：

  • 方法：

  1. 哈希表
  2. sort后，进行查找
1
2


21.调整数组顺序使奇数位于偶数前面

  • 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

  • 输入：

  • 输入：nums = [1,2,3,4]

  • 输出：[1,3,2,4]

  • 注：[3,1,2,4] 也是正确的答案之一。

  • 方法：

  1. 一次快排
  2. 快排需要注意：while右边先写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> exchange(vector<int>& nums) {
	//一次快速排序
	if (nums.size() == 0)
		return {};

	int L = 0;
	int R = nums.size() - 1;
	while (L != R) {
		while (L < R &&nums[L] % 2 == 1)
			L++;
		while (L < R &&nums[R] % 2 == 0)
			R--;
		if (L < R) {
			int temp = nums[R];
			nums[R] = nums[L];
			nums[L] = temp;
		}
	}
	return nums;
}

22.链表中倒数第k个节点

  • 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

  • 输入：

  • 给定一个链表: 1->2->3->4->5, 和 k = 2.

  • 返回链表 4->5.

  • 方法：

  1. vector保存所有结点
  2. 快慢指针，快指针先走K，然后慢指针开始走，sum - k = 要走的步数。
1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* getKthFromEnd(ListNode* head, int k) {
	ListNode* fast = head;
	ListNode* slow = head;
	while (k && fast) {
		fast = fast->next;
		k--;
	}
	while (fast) {
		fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

24.反转链表

  • 1.递归遍历到最后一个节点开始反转

  • 2.辅助指针逐步反转

    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
    ListNode* reverseList(ListNode* head) {
    	if (head == NULL || head->next == NULL)
    		return head;

    	ListNode* temp = head->next;
    	ListNode* newH = reverseList(temp);

    	temp->next = head;
    	head->next = NULL;

    	return newH;


    }

    // ListNode* reverseList(ListNode* head) {
    //     if(head==NULL || head->next==NULL)
    //         return head;

    //     ListNode* newH =NULL;
    //     ListNode* cur =head;

    //     while(cur){
    //         ListNode* temp= cur->next;
    //         cur->next = newH;
    //         newH = cur;
    //         cur = temp;
    //     }
    //     return newH;
    // }

25.合并两个排序的链表

  • 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

  • 输入：

  • 输入：1->2->4, 1->3->4

  • 输出：1->1->2->3->4->4

  • 方法：

  1. 类似归并排序，归的时候，逐步组成一个有序集合
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
32
33
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* pre = NULL;
	ListNode* head = NULL;
	if (l1 == NULL)return l2;
	if (l2 == NULL)return l1;
	if (l1->val <= l2->val) {
		pre = l1;
		l1 = l1->next;
	}
	else {
		pre = l2;
		l2 = l2->next;
	}
	head = pre;
	while (l1&&l2) {
		if (l1->val <= l2->val) {
			pre->next = l1;
			pre = pre->next;
			l1 = l1->next;
		}
		else {
			pre->next = l2;
			pre = pre->next;
			l2 = l2->next;
		}
	}
	if (l1)
		pre->next = l1;
	if (l2)
		pre->next = l2;

	return head;
}
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/07/20/jianzhioffer1/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！