0%

LeetCode算法经典题集(二)

标注

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problemset/algorithms/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

14.最长公共前缀(二分查找法/分治法)

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”

示例 2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

题解

水平扫描法

首先需要判空,看看字符串数组是否存在
接着,假设第一个字符串是公共前缀,从第二个字符串开始遍历,求出它们的公共子串

官方给出的是LCP结论:

  • LCP(S1…Sn) = LCP(LCP(LCP(S1,S2),S3),…Sn)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
String prefix = strs[0];
int len = prefix.length();
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, --len);
if (len == 0) {
return "";
}
}
}
return prefix;
}

算法分析:

  • 时间复杂度:O(S),S 是所有字符串中字符数量的总和
  • 空间复杂度:O(1),我们只需要使用常数级别的额外空间

水平扫描列

想象让字符串数组按列向左对齐,然后以第一个字符串的索引为基准水平扫描

如果长度达到某个字符串的最大值或者不匹配,就返回当前累积公共前缀

1
2
3
4
5
6
7
8
9
10
11
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
for (int i = 0; i < strs[0].length() ; i++){
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j ++) {
if (i == strs[j].length() || strs[j].charAt(i) != c)
return strs[0].substring(0, i);
}
}
return strs[0];
}

算法分析:

  • 时间复杂度:O(S),S 是所有字符串中字符数量的总和
  • 空间复杂度:O(1),我们只需要使用常数级别的额外空间

分治法

思路
这个算法的思路来自于LCP操作的结合律
我们可以发现 LCP(S1…Sn) = LCP(LCP(S1…Sk), LCP(Sk+1…Sn))
其中 LCP(S1…Sn) 是字符串 (S1…Sn) 的最长公共前缀, 1 < k < n

算法
为了应用上述的结论,我们使用分治的技巧,将原问题 LCP(Si…Sj) 分成两个子问题 LCP(Si…Smid) 与 LCP(Smid+1…Sj),其中 mid = (i + j) / 2

我们用子问题的解 lcpLeftlcpRight 构造原问题的解 LCP(Si…Sj)
从头到尾挨个比较 lcpLeft 与 lcpRight 中的字符,直到不能再匹配为止
计算所得的 lcpLeftlcpRight 最长公共前缀就是原问题的解 LCP(Si…Sj)

代码如下

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
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
if (l == r) {
return strs[l];
}
else {
int mid = (l + r)/2;
String lcpLeft = longestCommonPrefix(strs, l , mid);
String lcpRight = longestCommonPrefix(strs, mid + 1,r);
return commonPrefix(lcpLeft, lcpRight);
}
}

String commonPrefix(String left,String right) {
int min = Math.min(left.length(), right.length());
for (int i = 0; i < min; i++) {
if ( left.charAt(i) != right.charAt(i) )
return left.substring(0, i);
}
return left.substring(0, min);
}

算法分析:
最坏情况下,我们有 n 个长度为 m 的相同字符串

  • 时间复杂度:O(S),S 是所有字符串中字符数量的总和 S = m * n
    最好情况下,算法会进行 minLen * n 次比较,其中 minLen 是数组中最短字符串的长度
  • 空间复杂度:O(m * log(n)),内存开支主要是递归过程中使用的栈空间所消耗的。 一共会进行 log(n) 次递归,每次需要 m 的空间存储返回结果,所以空间复杂度为 O(m * log(n))

二分查找法

这个想法是应用二分查找法找到所有字符串的公共前缀的最大长度 L。 算法的查找区间是 (0…minLen),其中 minLen 是输入数据中最短的字符串的长度,同时也是答案的最长可能长度。 每一次将查找区间一分为二,然后丢弃一定不包含最终答案的那一个。算法进行的过程中一共会出现两种可能情况:

  • S[1...mid] 不是所有串的公共前缀。 这表明对于所有的 j > iS[1..j] 也不是公共前缀,于是我们就可以丢弃后半个查找区间。

  • S[1...mid] 是所有串的公共前缀。 这表示对于所有的 i < jS[1..i] 都是可行的公共前缀,因为我们要找最长的公共前缀,所以我们可以把前半个查找区间丢弃

代码如下

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
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0)
return "";
int minLen = Integer.MAX_VALUE;
for (String str : strs)
minLen = Math.min(minLen, str.length());
int low = 1;
int high = minLen;
while (low <= high) {
int middle = (low + high) / 2;
if (isCommonPrefix(strs, middle))
low = middle + 1;
else
high = middle - 1;
}
return strs[0].substring(0, (low + high) / 2);
}

private boolean isCommonPrefix(String[] strs, int len){
String str1 = strs[0].substring(0,len);
for (int i = 1; i < strs.length; i++)
if (!strs[i].startsWith(str1))
return false;
return true;
}

15.三数之和(双指针法)

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

题解

暴力解

三重for循环遍历出所有结果,不过这种做法会超时,因为数据量可能会很大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
List<List<Integer>> lists = new ArrayList<>();
if (len < 3 ) {
return lists;
}
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
for (int k = j + 1; k < len; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
if (!lists.contains(list)) {
lists.add(list);
}
}
}
}
}
return lists;
}

算法分析:

  • 时间复杂度:O(n3)
  • 空间复杂度:O(1)

双指针法

一开始,判断数组长度是否大等于3,否则直接返回空集

在遍历数组之前,用Arrays.sort()方法对数组排序,方便后续操作

使用for循环遍历数组,每次遍历设置两个指针lr

l = i + 1 指向下一个元素
r = len - 1 指向最后一个元素

l < r时,不断递增指针l与递减指针r,并判断ilr三个索引下的三数和是否为0

若和为0,同时递增指针l与递减指针r
若和小于0,递增指针l
若和大于0,递减指针r

当然,步骤中间需要去重,防止结果重复

代码如下

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
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
List<List<Integer>> lists = new ArrayList<>();
if (len < 3 ) {
return lists;
}
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
// 如果当前的数大于0,那么和一定大于0
if (nums[i] > 0) {
break;
}
// 这一步为了去重,i > 0 防止越界
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int l = i + 1;
int r = len - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum == 0) {
lists.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
l++;
r--;
} else if (sum < 0) {
l++;
} else {
r--;
}
}
}
return lists;
}

算法分析:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

17.电话号码的字母组合(回溯法)

题目

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例:

输入:”23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

题解(回溯法)

这题采用回溯的思想,虽然题解写的蛮像递归的

回溯是一种通过穷举所有可能情况来找到所有解的算法。
如果一个候选解最后被发现并不是可行解,回溯算法会舍弃它,并在前面的一些步骤做出一些修改,并重新尝试找到可行解

给出如下回溯函数 backtrack(combination, next_digits) ,它将一个目前已经产生的组合 combination 和接下来准备要输入的数字 next_digits 作为参数

如果没有更多的数字需要被输入,那意味着当前的组合已经产生好了

如果还有数字需要被输入:

  • 遍历下一个数字所对应的所有映射的字母
  • 将当前的字母添加到组合最后,也就是 combination += letter
  • 重复这个过程,输入剩下的数字: backtrack(combination + letter, next_digits[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
34
35
36
37
class Solution {
// 使用匿名内部类的方式创建 Map 对象 phone
Map<String, String> phone = new HashMap<String, String>() {{
put("2", "abc");
put("3", "def");
put("4", "ghi");
put("5", "jkl");
put("6", "mno");
put("7", "pqrs");
put("8", "tuv");
put("9", "wxyz");
}};

List<String> list = new ArrayList<>();

public void backtrack(String combination, String next_digits) {
if (next_digits.length() == 0) {
// 如果该轮穷举完毕,那么添加结果
list.add(combination);
} else { // 若还能继续递归调用
String digit = next_digits.substring(0, 1);
String letters = phone.get(digit);
int len = letters.length();
for (int i = 0; i < len; i++) {
String letter = phone.get(digit).substring(i, i + 1);
backtrack(combination + letter, next_digits.substring(1));
}
}
}

public List<String> letterCombinations(String digits) {
if (digits.length() != 0) {
backtrack("", digits);
}
return list;
}
}

19.删除链表的倒数第N个节点(双指针法)

题目

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

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

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明:

给定的 n 保证是有效的。

进阶:

你能尝试使用一趟扫描实现吗?

题解

暴力法-两次遍历

在第一次遍历中,我们找出列表的长度 L

然后设置另一个指针,移动它遍历列表,直至它到达第 (L - n)个结点那里

把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2) 个结点,完成这个算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode first = head;
while (first != null) {
length++;
first = first.next;
}
length -= n;
first = dummy;
while (length > 0) {
length--;
first = first.next;
}
first.next = first.next.next;
return dummy.next;
}

算法分析:

  • 时间复杂度:O(L)
  • 空间复杂度:O(1)

双指针法

优化暴力法为一次遍历,即使用两个指针同步移动

算法巧妙之处也也在于设置了一个哑节点dummy,另其指向头节点

设置第一个指针go,第二个指针target

第一个指针go从列表的开头向前移动 n + 1 步,第二个指针target将从列表的头出发,此时,这两个指针被 n 个结点隔开

通过同时移动两个指针向前来保持这个恒定的间隔,直到go指针到达最后一个结点

此时target指针指向从最后一个结点数起的第 n 个结点。我们重新链接target指针所引用的结点的 next 指针指向该结点的下下个结点

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode removeNthFromEnd(ListNode head, int n) {
// 设置一个哑节点
ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode go = dummy;
ListNode target = dummy;

// 先让 go 指针前移
for (int i = 0; i < n + 1; i++) {
go = go.next;
}

// 两个指针同步移动
while (go != null) {
go = go.next;
target = target.next;
}

target.next = target.next.next;

return dummy.next;
}

算法分析:

  • 时间复杂度:O(L)
  • 空间复杂度:O(1)

22.括号生成(深度优先搜索/回溯法/闭合数)

题目

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

题解

暴力法-深度优先搜索

思路简单的深度优先搜索

此前,需要一个方法判断字符数组是否有效 —— isValid()

方法描述:设置一个整形变量balance,遍历数组,看看左右括号的位置是否权衡,遇到左括号balance++,反之balance--
一旦balance < 0,说明数组是无效的

接着写一个深度优先的方法generate
首先,通过当前字符数组长度curlen判断是否达到最大深度max

  • 达到,则判断组合是否时有效括号组
  • 没达到,继续遍历

接着给出下一位括号字符的两种可能,进行搜索匹配,递归调用

代码如下

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
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<>();
generate(combinations, 0, n * 2, new char[2 * n]);
return combinations;
}

public void generate(List<String> result, int curLen, int max, char[] curComb) {
if (curLen == max) {
if (isValid(curComb)) {
result.add(new String(curComb));
}
} else {
curComb[curLen] = '(';
generate(result, curLen + 1, max, curComb);
curComb[curLen] = ')';
generate(result, curLen + 1, max, curComb);
}
}

public boolean isValid(char[] check) {
int balance = 0;
for (char c: check) {
if (c == '(') {
balance++;
} else {
balance--;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}

算法分析:

  • 时间复杂度:O(n * 22n)
  • 空间复杂度:O(n * 22n)

回溯法

可以对算法进行小优化,只有在知道当前字符数组是有效的情况下才选择性添加下一个括号字符

这就可以通过跟踪到目前为止放置的左括号数目open和右括号数目close来做到这一点

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
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}

/**
* 回溯法函数 backtrack
* @param ans 结果集
* @param cur 当前字符串
* @param open 左括号数量
* @param close 右括号数量
* @param max 左/右括号最大数量
*/
public void backtrack(List<String> ans, String cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max) {
backtrack(ans, cur + "(", open + 1, close, max);
}
if (close < open) {
backtrack(ans, cur + ")", open, close + 1, max);
}
}

算法分析:
复杂度分析依赖于理解 generateParenthesis(n) 中有多少个元素,这个分析超出了本文的范畴,但事实证明这是第 n 个卡塔兰数

  • 时间复杂度:O(4n / √n)
  • 空间复杂度:O(4n / √n)

闭合数

思路

为了枚举某些内容,我们通常希望将其表示为更容易计算的不相交子集的总和。

考虑有效括号序列 S 的 闭包数:至少存在 index >= 0,使得 S[0], S[1], …, S[2 * index + 1]是有效的。 显然,每个括号序列都有一个唯一的闭包号。 我们可以尝试单独列举它们。

算法

对于每个闭合数 c,我们知道起始和结束括号必定位于索引 02 * c + 1。然后两者间的 2 * c 个元素一定是有效序列,其余元素一定是有效序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left: generateParenthesis(c)) {
for (String right : generateParenthesis(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
return ans;
}

算法分析:与回溯法类似

  • 时间复杂度:O(4n / √n)
  • 空间复杂度:O(4n / √n)

23.合并K个排序链表(分治法)

题目

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

题解

暴力法

  1. 遍历所有链表,将所有节点的值放到一个数组中
  2. 将这个数组排序,然后遍历所有元素得到正确顺序的值
  3. 用遍历得到的值,创建一个新的有序链表

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < lists.length; i++) {
while (lists[i] != null) {
list.add(lists[i].val);
lists[i] = lists[i].next;
}
}
Collections.sort(list);
ListNode tmp = new ListNode(0);
ListNode dummy = tmp;
for (int x: list) {
tmp.next = new ListNode(x);
tmp = tmp.next;
}
return dummy.next;
}

算法分析:(n为元素总个数)

  • 时间复杂度:O(n * log(n)),稳定的排序花费的时间
  • 空间复杂度:O(n)

分治法

k 个链表两两配对,每次合并一对链表,合并通过mergeTwoLists函数

每轮合并完,需要操作的链表数目就减少一半

第一轮合并以后,k 个链表被合并成了 k/2 个链表,平均长度为2N/k
​第二轮是 k/4个链表,第三轮k/8个,等等

重复这一过程,直到我们得到了最终的有序链表。

在每一次配对合并的过程中都会遍历几乎全部 N 个节点,并重复这一过程 log2k 次

代码如下

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
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
int interval = 1;
while (interval < len) {
for (int i = 0; i < len - interval; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
interval *= 2;
}
return len > 0 ? lists[0] : null;
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode point = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
point.next = l1;
l1 = l1.next;
} else {
point.next = l2;
l2 = l1;
l1 = point.next.next;
}
point = point.next;
}
if (l1 == null) {
point.next=l2;
} else {
point.next=l1;
}
return head.next;
}

算法分析:

  • 时间复杂度:O(n * log2k)
  • 空间复杂度:O(1)

24.两两交换链表中的节点(递归法)

题目

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

递归法

从链表的头节点 head 开始递归

每次递归都负责交换一对节点,这对节点由 firstsecond 表示

下一次递归传递下一对需要交换的节点,若链表中还有节点,就继续递归

交换了两个节点以后,返回节点 second,因为它是交换后的新头节点

在所有节点交换完成以后,我们返回交换后的头头节点

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode first = head;
ListNode second = head.next;

first.next = swapPairs(second.next);
second.next = first;

return second;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

迭代法

以迭代的方式不断交换两个节点:把链表分为两部分,奇数节点部分,偶数节点部分,A 指的是交换节点中的前节点,B 指的是要交换节点中的后节点

为完成它们的交换,这里需要引入一个节点prevNode作为A的前驱节点

firstNode代表A节点
secondNode代表B节点

while循环实现迭代,一边迭代一边更新下一轮需要迭代的节点

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
public ListNode swapPairs(ListNode head) {
// Dummy node acts as the prevNode for the head node
// of the list and hence stores pointer to the head node.
ListNode dummy = new ListNode(-1);
dummy.next = head;

ListNode prevNode = dummy;

while ((head != null) && (head.next != null)) {

// Nodes to be swapped
ListNode firstNode = head;
ListNode secondNode = head.next;

// Swapping
prevNode.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;

// Reinitializing the head and prevNode for next swap
prevNode = firstNode;
head = firstNode.next; // jump
}

// Return the new head node.
return dummy.next;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

25.K 个一组翻转链表 | 较难(递归)

题目

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换

题解

利用栈结构

利用栈解题,时间、空间效率都不高

首先,用 Stack<ListNode> stack来构造一个栈

遍历链表,每次都通过push操作进栈,同时设置一个计数器index

当遍历次数达到k时,pop出栈,实现链表k位反转,重置计数器
若没达到k,说明到达链表尾部,直接结束即可
只需注意指针的指向

代码如下

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
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1 || head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tmp = dummy;
Stack<ListNode> stack = new Stack<>();
int index = 0;

while (head != null) {
stack.push(head);
head = head.next;
index++;
if (index == k) {
for (int i = 0; i < k; i++) {
tmp.next = stack.pop();
tmp = tmp.next;
}
tmp.next = head;
index = 0;
}
}
tmp.next = index != 0 ? stack.firstElement() : null;

return dummy.next;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(k)

优化

反转过程不借助栈结构实现,利用while循环实现链表反转,这里写一个方法reverse

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
public ListNode reverseKGroup(ListNode head, int k) {
if (k == 1 || head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode last = dummy;
ListNode pre = dummy;

int index = 0;
while (last.next != null) {
last = last.next;
index++;
if (index == k) {
ListNode tail = last.next;
ListNode start = pre.next;
last.next = null;
pre.next = reverse(start);
start.next = tail;
pre = start;
last = pre;
index = 0;
}
}
return dummy.next;
}

public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}

算法分析:

  • 时间复杂度:O(n * k)
  • 空间复杂度:O(1)

递归

在将递归之前,先讲一下这个算法的reverse函数

传递的参数是preend
pre:待反转链表的哑指针
end:待反转链表的最后一个节点

附上流程图

递归思路:
1)先设置一个哑节点dummy
2)设置尾节点end
3)尾节点end移动k
4)另尾节点endnext下一个节点为经过函数reverseKGroup反转过的节点
5)对dummyend之间的节点进行反转
6)返回新的头节点dummy.next

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 reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode end = dummy;
for (int i = 0; i < k; i++) {
end = end.next;
if (end == null) {
return dummy.next;
}
}
end.next = reverseKGroup(end.next, k);
dummy.next = reverse(dummy, end);
return dummy.next;
}

ListNode reverse(ListNode pre, ListNode end) {
ListNode tail = end.next;
ListNode cur = pre.next;
ListNode finish = tail;
while (pre.next != finish) {
pre.next = cur.next;
cur.next = tail;
tail = cur;
cur = pre.next;
}
return tail;
}

算法分析:

  • 时间复杂度:O(n * k)
  • 空间复杂度:O(n * k)