開(kāi)個(gè)新坑嗽交，準(zhǔn)備校招研發(fā)崗面試篮幢，基本的算法還是要過(guò)關(guān)的。
寫(xiě)在前面
- 本系列包含《劍指Offer》66道算法題穷缤，預(yù)計(jì)一周刷完敌蜂。
系列匯總：劍指Offer 66題 Java 刷題筆記匯總 - 所有題目均可在牛客網(wǎng)在線(xiàn)編程平臺(tái)進(jìn)行調(diào)試津肛。
網(wǎng)址：https://www.nowcoder.com/ta/coding-interviews - 本系列包含題目章喉，解題思路及代碼（Java）。
代碼同步發(fā)布在GitHub：https://github.com/JohnnyJYWu/offer-Java
下一篇：算法 | 一周刷完《劍指Offer》 Day2：第17~26題
Day1：第1~16題
后面總會(huì)遇到難的繞的題身坐，前兩天多做幾道秸脱，總不會(huì)虧的。
- T1. 二維數(shù)組中的查找
- T2. 替換空格
- T3. 從尾到頭打印鏈表
- T4. 重建二叉樹(shù)
- T5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
- T6. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
- T7. 斐波那契數(shù)列
- T8. 跳臺(tái)階
- T9. 變態(tài)跳臺(tái)階
- T10. 矩陣覆蓋
- T11. 二進(jìn)制中 1 的個(gè)數(shù)
- T12. 數(shù)值的整數(shù)次方
- T13. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
- T14. 鏈表中倒數(shù)第 K 個(gè)結(jié)點(diǎn)
- T15. 反轉(zhuǎn)鏈表
- T16. 合并兩個(gè)排序的鏈表
T1. 二維數(shù)組中的查找
題目描述
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同）部蛇，每一行都按照從左到右遞增的順序排序摊唇，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)涯鲁，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)巷查，判斷數(shù)組中是否含有該整數(shù)。
解題思路
因?yàn)榫仃囍械拿恳粋€(gè)數(shù)抹腿，左邊都比它小岛请，下邊都比它大。因此警绩，從右上角開(kāi)始查找崇败，就可以根據(jù) target 和當(dāng)前元素的大小關(guān)系來(lái)縮小查找區(qū)間。
public boolean Find(int target, int[][] array) {
if(array == null || array.length == 0 || array[0].length == 0) {
return false;
}
int m = 0, n = array[0].length - 1;//從右上角開(kāi)始找房蝉，array[0][n-1]
while(m <= array.length - 1 && n >= 0) {
if(target == array[m][n])
return true;
else if(target > array[m][n])
m ++;
else
n --;
}
return false;
}
T2. 替換空格
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)僚匆，將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如搭幻，當(dāng)字符串為We Are Happy，則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy逞盆。
解題思路
由于每個(gè)空格替換成了三個(gè)字符檀蹋，首先要擴(kuò)容字符串長(zhǎng)度至替換后的長(zhǎng)度，因此當(dāng)遍歷到一個(gè)空格時(shí)，需要在尾部填充兩個(gè)任意字符俯逾。
然后聲明兩個(gè)下標(biāo)贸桶，一個(gè)為原字符串末尾下標(biāo) i，一個(gè)為現(xiàn)字符串末尾 j桌肴，兩個(gè)下標(biāo)同步從后往前掃皇筛。當(dāng) i 指向空格時(shí)，j 就倒著依次添加 '0', '2', '%'坠七。
這樣做的目的是： j 下標(biāo)不會(huì)超過(guò) i 下標(biāo)水醋，不會(huì)影響原字符串的內(nèi)容。
public String replaceSpace(StringBuffer str) {
int oldLen = str.length();
for(int i = 0; i < oldLen; i ++) {
if(str.charAt(i) == ' ') {//每出現(xiàn)一個(gè)空格彪置，在結(jié)尾添加兩個(gè)任意字符拄踪，擴(kuò)充字符串長(zhǎng)度
str.append("12");
}
}
int i = oldLen - 1;
int j = str.length() - 1;
while(i >= 0 && j > i) {
char c = str.charAt(i);
i --;
if(c == ' ') {//每出現(xiàn)一個(gè)空格，替換為%20
str.setCharAt(j, '0');
j --;
str.setCharAt(j, '2');
j --;
str.setCharAt(j, '%');
j --;
} else {//否則照舊
str.setCharAt(j, c);
j --;
}
}
return str.toString();
}
T3. 從尾到頭打印鏈表
題目描述
輸入一個(gè)鏈表拳魁，按鏈表值從尾到頭的順序返回一個(gè)ArrayList惶桐。
解題思路
使用棧實(shí)現(xiàn)：先入后出。全部入棧潘懊，依次出棧姚糊，順序即為從尾到頭。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用棧實(shí)現(xiàn)授舟，先入后出
Stack<Integer> stack = new Stack<>();
ArrayList<Integer> arrayList = new ArrayList<>();
while(listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while(!stack.isEmpty()) {
arrayList.add(stack.pop());
}
return arrayList;
}
使用遞歸實(shí)現(xiàn)：先加入鏈表后面的結(jié)點(diǎn)叛拷，再加入當(dāng)前結(jié)點(diǎn)，順序即為從尾到頭岂却。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//使用遞歸實(shí)現(xiàn)忿薇，先加入鏈表后面的結(jié)點(diǎn)，再加入當(dāng)前結(jié)點(diǎn)
ArrayList<Integer> arrayList = new ArrayList<>();
if(listNode != null) {
arrayList.addAll(printListFromTailToHead(listNode.next));//先遞歸
arrayList.add(listNode.val);//再加入當(dāng)前
}
return arrayList;
}
T4. 重建二叉樹(shù)
題目描述
輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果躏哩，請(qǐng)重建出該二叉樹(shù)署浩。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}扫尺，則重建二叉樹(shù)并返回筋栋。
解題思路
首先清楚以下性質(zhì)：
前序遍歷：根 -> 左 -> 右，中序遍歷：左 -> 根 -> 右正驻。
因此一顆二叉樹(shù)中弊攘，前序遍歷的第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，通過(guò)它在中序遍歷中的位置姑曙，可以將中序遍歷分為兩部分襟交，左半部分是該結(jié)點(diǎn)的左子樹(shù)，右半部分是該結(jié)點(diǎn)的右子樹(shù)伤靠。
根據(jù)這個(gè)原理捣域，遞歸執(zhí)行即可重構(gòu)出二叉樹(shù)。
private Map<Integer, Integer> map = new HashMap<>();//用于查找中序遍歷數(shù)組中，每個(gè)值對(duì)應(yīng)的索引
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
for(int i = 0; i < in.length; i ++) {
map.put(in[i], i);//key: in的值焕梅，value: 值在in中位置
}
return getBiTree(pre, 0, pre.length - 1,
in, 0, in.length - 1);
}
private TreeNode getBiTree(int[] pre, int preLeft, int preRight, //前序遍歷及當(dāng)前在前序遍歷中的區(qū)間
int[] in, int inLeft, int inRight) { //中序遍歷及當(dāng)前在前序遍歷中的區(qū)間
if(preLeft == preRight) { //即根據(jù)前序遍歷迹鹅，當(dāng)前結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)
return new TreeNode(pre[preLeft]);
}
if(preLeft > preRight || inLeft > inRight) {
return null;
}
TreeNode root = new TreeNode(pre[preLeft]);
int inIndex = map.get(root.val);
int leftTreeSize = inIndex - inLeft;//該結(jié)點(diǎn)左半部分的結(jié)點(diǎn)數(shù)
//遞歸，獲取左子樹(shù)及右子樹(shù)
root.left = getBiTree(pre, preLeft + 1, preLeft + leftTreeSize, //左半部分在前序遍歷中的區(qū)間
in, inLeft, inIndex - 1);//左半部分在中序遍歷中的區(qū)間
root.right = getBiTree(pre, preLeft + 1 + leftTreeSize, preRight, //右半部分在前序遍歷中的區(qū)間
in, inIndex + 1, inRight);//右半部分在中序遍歷中的區(qū)間
return root;
}
T5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
題目描述
用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列贞言，完成隊(duì)列的Push和Pop操作斜棚。 隊(duì)列中的元素為int類(lèi)型。
解題思路
隊(duì)列：先進(jìn)先出该窗，棧：先進(jìn)后出
例如弟蚀，假設(shè) 1 ~ n 的數(shù)字順序，入Stack1挪捕，出的順序?yàn)?n ~ 1 粗梭。
這時(shí)，Stack1出棧進(jìn)入Stack2级零，進(jìn)入Stack2的順序?yàn)閚 ~ 1断医，那么Stack2出的順序?yàn)?1 ~ n 。
相當(dāng)于隊(duì)列 1 ~ n 進(jìn)奏纪， 1 ~ n 出鉴嗤。
Stack<Integer> stack1 = new Stack<Integer>();//stack1入棧時(shí)使用
Stack<Integer> stack2 = new Stack<Integer>();//stack2出棧時(shí)使用，直接出棧即可
public void push(int node) {
while(!stack2.isEmpty()) {//先將stack2中所有元素壓入stack1
stack1.push(stack2.pop());
}
stack1.push(node);//然后將當(dāng)前要進(jìn)入隊(duì)列元素壓入stack1
while(!stack1.isEmpty()) {//最后將stack1所有元素壓入stack2
stack2.push(stack1.pop());//此時(shí)stack2中出棧順序即為隊(duì)列出棧順序序调，相當(dāng)于先入先出
}
}
public int pop() {
return stack2.pop();
}
T6. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
題目描述
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾醉锅，我們稱(chēng)之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)发绢，輸出旋轉(zhuǎn)數(shù)組的最小元素硬耍。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1边酒。 NOTE：給出的所有元素都大于0经柴，若數(shù)組大小為0，請(qǐng)返回0墩朦。
解題思路
我們可以認(rèn)為數(shù)組分成了兩部分坯认，前半部分是較大的數(shù)，后半部分是較小的數(shù)氓涣。
利用二分查找的思路牛哺，觀(guān)察取中的數(shù)在前半部分還是后半部分，以此來(lái)找出最小的數(shù)（后半部分的第一個(gè)數(shù)）劳吠。
public int minNumberInRotateArray(int[] array) {
if(array.length == 0) {
return 0;
}
//二分查找
int low = 0, high = array.length - 1;
while (array[low] >= array[high]) {
if(high - low == 1) {
return array[high];
}
int mid = low + (high - low) / 2;//取中
if(array[mid] >= array[low]) {//此時(shí)mid在前半?yún)^(qū)大的數(shù)里
low = mid;
} else {//此時(shí)mid在后半?yún)^(qū)小的數(shù)里
high = mid;
}
}
return array[low];
}
T7. 斐波那契數(shù)列
題目描述
大家都知道斐波那契數(shù)列引润，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開(kāi)始赴背，第0項(xiàng)為0）椰拒。n<=39
解題思路
斐波那契數(shù)列：F[n]=F[n-1]+F[n-2] (n>=3,F[1]=1,F[2]=1)
注意：此題要求F[1]=0晶渠。
public int Fibonacci(int n) {//n<=39
int[] array = new int[40];
array[0] = 0;
array[1] = 1;
for(int i = 2; i < array.length; i ++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
T8. 跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階凰荚，也可以跳上2級(jí)燃观。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）。
解題思路
動(dòng)態(tài)規(guī)劃的思想便瑟。這里采用倒著往前推的方法遞減target缆毁，最后一次跳1或最后一次跳2，倒著往前遞歸到涂。
public int JumpFloor(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
if(target == 2) {
return 2;
}
if(target > 2) {//遞歸求可能出現(xiàn)的情況總數(shù)（最后一次跳1或最后一次跳2脊框，倒著往前推）
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
return 0;
}
或者，其本質(zhì)上是斐波那契數(shù)列的原理践啄。
public int JumpFloor(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
int[] array = new int[target];
array[0] = 1;
array[1] = 2;
for (int i = 2; i < target; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[target - 1];
}
T9. 變態(tài)跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階浇雹，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法屿讽。
解題思路
同理昭灵，動(dòng)態(tài)規(guī)劃的思想，遞歸求解伐谈。（這次情況有點(diǎn)多烂完，用到循環(huán)了）
public int JumpFloorII(int target) {
if(target == 0 || target == 1) {
return 1;
}
if(target == 2) {
return 2;
}
int sum = 0;
for(int i = 0; i < target; i ++) {//本次跳0次到跳target-1次
sum += JumpFloorII(i);//對(duì)于本次的跳躍又有多少種跳法？遞歸獲取結(jié)果
}
return sum;
}
T10. 矩陣覆蓋
題目描述
我們可以用 2 * 1 的小矩形橫著或者豎著去覆蓋更大的矩形诵棵。請(qǐng)問(wèn)用n個(gè) 2 * 1 的小矩形無(wú)重疊地覆蓋一個(gè) 2 * n 的大矩形抠蚣，總共有多少種方法？
解題思路
原理同T8履澳，詳見(jiàn)圖片嘶窄。
public int RectCover(int target) {
if(target == 0) {
return 0;
}
if(target == 1) {
return 1;
}
int[] array = new int[target];
array[0] = 1;
array[1] = 2;
for (int i = 2; i < target; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[target - 1];
}
T11. 二進(jìn)制中 1 的個(gè)數(shù)
題目描述
輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)距贷。其中負(fù)數(shù)用補(bǔ)碼表示柄冲。
解題思路
Integer.bitCount(n)：技術(shù)整型的二進(jìn)制表示中1的個(gè)數(shù)。储耐。羊初。
public int NumberOf1(int n) {//（？什湘？长赞？）
return Integer.bitCount(n);
}
正常算法：&按位與。每次將 n 和 n-1 進(jìn)行 & 運(yùn)算闽撤，從右往左去掉二進(jìn)制最右邊的一個(gè)1得哆。例如：
n: 100100
n - 1: 100011
n & (n-1): 100000
一次運(yùn)算后，n由100100變?yōu)?00000哟旗，去除了一個(gè)1贩据。所有1去完時(shí)栋操，n為0。
public int NumberOf1(int n) {//正常算法
int sum = 0;
while(n != 0) {
sum ++;
n = n & (n-1);//&按位與
}
return sum;
}
T12. 數(shù)值的整數(shù)次方
題目描述
給定一個(gè)double類(lèi)型的浮點(diǎn)數(shù)base和int類(lèi)型的整數(shù)exponent饱亮。求base的exponent次方矾芙。
解題思路
由于xn = (x*x)n/2，通過(guò)遞歸求解可減小時(shí)間復(fù)雜度近上，每遞歸一次剔宪，n 減一半。時(shí)間復(fù)雜度O(logn)壹无。
注意：需要小心 n 的正負(fù)葱绒、奇偶。
public double Power(double base, int exponent) {
if(exponent == 0) return 1;
if(exponent == 1) return base;
boolean isPositive = true;//正負(fù)次方以此判斷
if(exponent < 0) {
exponent = -exponent;
isPositive = false;
}
double pow = Power(base * base, exponent / 2);//遞歸斗锭，每次遞歸n減小一半地淀，即 (x*x)^(n/2)
if(exponent % 2 != 0) pow *= base;//奇次冪的話(huà)，/2會(huì)少算一次岖是，在這補(bǔ)回來(lái)
return isPositive ? pow : (1 / pow);//三元表達(dá)式帮毁，正次冪為pow，負(fù)次冪為1/pow
}
T13. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
題目描述
輸入一個(gè)整數(shù)數(shù)組璧微，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序作箍，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分前硫，并保證奇數(shù)和奇數(shù)胞得，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
解題思路
先統(tǒng)計(jì)奇偶數(shù)的個(gè)數(shù)屹电。在所要求的數(shù)組中阶剑，奇數(shù)的個(gè)數(shù)即為數(shù)組中偶數(shù)應(yīng)該開(kāi)始儲(chǔ)存的位置。
clone一個(gè)數(shù)組危号，按順序往原數(shù)組里存牧愁，奇數(shù)存前面，偶數(shù)存后面外莲。
public void reOrderArray(int[] array) {
int oddNum = 0;
for(int value: array) {
if(value % 2 == 1) {
oddNum++;
}
}
int[] copyArray = array.clone();//克隆數(shù)組猪半，對(duì)原數(shù)組賦值
int i = 0, j = oddNum;//j為偶數(shù)開(kāi)始存儲(chǔ)的位置
for(int num : copyArray) {
if(num % 2 == 1) {
array[i] = num;
i ++;
} else {
array[j++] = num;
j ++;
}
}
}
或者，聲明兩個(gè)ArrayList存奇數(shù)和偶數(shù)偷线，然后合并磨确。
public void reOrderArray(int[] array) {
ArrayList<Integer> odd = new ArrayList<>();
ArrayList<Integer> even = new ArrayList<>();
for(int i = 0; i < array.length; i ++) {
if(array[i] % 2 == 0) {
even.add(array[i]);
} else {
odd.add(array[i]);
}
}
odd.addAll(even);
for(int i = 0; i < array.length; i ++) {
array[i] = odd.get(i);
}
}
T14. 鏈表中倒數(shù)第 K 個(gè)結(jié)點(diǎn)
題目描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)声邦。
解題思路
假設(shè)乏奥，共 n 個(gè)結(jié)點(diǎn)，倒數(shù)第k個(gè)結(jié)點(diǎn)即為第 n-k+1 個(gè)結(jié)點(diǎn)亥曹。
定義兩個(gè)指針node1和node2邓了，使他們都指向第一個(gè)結(jié)點(diǎn)恨诱。到第 n-k+1 個(gè)結(jié)點(diǎn)則需要移動(dòng) n-k次。
此時(shí)骗炉，node1移動(dòng)n次會(huì)指向空照宝。
先讓node1移動(dòng) k 次，還剩 n-k 次指向空痕鳍。
這時(shí)硫豆，node2與node1同步移動(dòng)龙巨，當(dāng)node1指空時(shí)笼呆，node2移動(dòng)了 n-k 次，剛好到第 n-k+1 個(gè)結(jié)點(diǎn)旨别。
public ListNode FindKthToTail(ListNode head, int k) {
if(head == null) return null;
ListNode node1 = head;
ListNode node2 = head;
while(node1 != null && k > 0) {//node1移動(dòng)k次诗赌，還有n-k次會(huì)指空
node1 = node1.next;
k --;
}
if(k > 0) return null;
while(node1 != null) {//移動(dòng)n-k次，此時(shí)node2到n-k+1個(gè)結(jié)點(diǎn)秸弛，即倒數(shù)第k個(gè)結(jié)點(diǎn)
node1 = node1.next;
node2 = node2.next;
}
return node2;
}
T15. 反轉(zhuǎn)鏈表
題目描述
輸入一個(gè)鏈表铭若，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭递览。
解題思路
關(guān)鍵在于聲明一個(gè)結(jié)點(diǎn)preNode用來(lái)記錄前一個(gè)結(jié)點(diǎn)叼屠，使下一次循環(huán)時(shí)的結(jié)點(diǎn)的next指向它，反轉(zhuǎn)順序绞铃。
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode preNode = null;
while(head != null) {
ListNode tmp = head.next;//tmp記錄【下一個(gè)結(jié)點(diǎn)】
head.next = preNode;//【當(dāng)前結(jié)點(diǎn)】的next指向【前一個(gè)結(jié)點(diǎn)】镜雨，反轉(zhuǎn)鏈表順序
preNode = head;//preNode記錄【當(dāng)前結(jié)點(diǎn)】，即【下一個(gè)結(jié)點(diǎn)】的【前一個(gè)結(jié)點(diǎn)】
head = tmp;//將【當(dāng)前結(jié)點(diǎn)】更改為【下一個(gè)結(jié)點(diǎn)】儿捧，進(jìn)入下一次循環(huán)
}
//當(dāng)head為null時(shí)跳出了循環(huán)荚坞，此時(shí)它的前一個(gè)結(jié)點(diǎn)preNode即為原鏈表的最后一個(gè)結(jié)點(diǎn)，鏈表順序已反轉(zhuǎn)
return preNode;
}
T16. 合并兩個(gè)排序的鏈表
題目描述
輸入兩個(gè)單調(diào)遞增的鏈表菲盾，輸出兩個(gè)鏈表合成后的鏈表颓影，當(dāng)然我們需要合成后的鏈表滿(mǎn)足單調(diào)不減規(guī)則。
解題思路
聲明一個(gè)新鏈表懒鉴，不斷比較原來(lái)兩個(gè)鏈表的 val 值诡挂，小的插入新鏈表即可。
注意：要求返回的表頭是聲明的鏈表的next結(jié)點(diǎn)临谱。
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-9999);
ListNode tmp = head;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {//比較兩個(gè)鏈表當(dāng)前結(jié)點(diǎn)的值璃俗，小的先插入新鏈表
tmp.next = list1;
list1 = list1.next;
} else {
tmp.next = list2;
list2 = list2.next;
}
tmp = tmp.next;
}
//容錯(cuò)，將剩余鏈表補(bǔ)到新鏈表結(jié)尾吴裤，此時(shí)能保持單調(diào)不減
if(list1 != null) tmp.next = list1;
if(list2 != null) tmp.next = list2;
return head.next;//記得head為聲明的無(wú)意義表頭旧找，head.next才是新鏈表的頭
}
項(xiàng)目地址：https://github.com/JohnnyJYWu/offer-Java
下一篇：算法 | 一周刷完《劍指Offer》 Day2：第17~26題
希望這篇文章對(duì)你有幫助~
