每日LeetCode力扣（21~25） _Leetcode

业无高卑志当坚，男儿有求安得闲？这篇文章主要讲述每日LeetCode力扣（21~25）相关的知识，希望能为你提供帮助。
21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1-> 2-> 4, 1-> 3-> 4
输出：1-> 1-> 2-> 3-> 4-> 4

解题

fun _0021_mergeTwoLists()
println("--------_0021_mergeTwoLists-------")
mergeTwoLists(
ListNode(1, ListNode(2, ListNode(4))),
ListNode(1, ListNode(3, ListNode(4)))
)?.print()

/**
* 递归写法，当某个链表为空了，就返回另一个。然后核心还是比较当前两个节点值大小，如果 l1 的小，
* 那么对于 l1 的下一个节点和 l2 调用递归函数，将返回值赋值给 l1.next，然后返回 l1；
* 否则就对于 l2 的下一个节点和 l1 调用递归函数，将返回值赋值给 l2.next，然后返回 l2
*/
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode?
if (l1 == null) return l2
if (l2 == null) return l1
return if (l1.data < l2.data)
l1.next = mergeTwoLists(l1.next, l2); l1
else
l2.next = mergeTwoLists(l1, l2.next); l2

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

解题

fun _0022_generateParenthesis()
println("--------_0022_generateParenthesis-------")
println(generateParenthesis(1))
println(generateParenthesis(2))
println(generateParenthesis(3))
println(generateParenthesis(4))

/**
* 思想是找左括号，每找到一个左括号，就在其后面加一个完整的括号，最后再在开头加一个 ()，就形成了所有的情况，
* 需要注意的是，有时候会出现重复的情况，所以用set数据结构，好处是如果遇到重复项，不会加入到结果中，
* 最后我们再把set转为vector即可
*/
fun generateParenthesis(n: Int): List< String>
val res = HashSet< String> ()
if (n == 0)
res.add("")
else
val pre = generateParenthesis(n - 1)
for (str in pre)
var str = str
for (i in str.indices)
if (str[i] == ()
str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length)
res.add(str)
str = str.substring(0, i + 1) + str.substring(i + 3, str.length)

res.add("()$str")

return res.toList()

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1-> 4-> 5,
1-> 3-> 4,
2-> 6
]
将它们合并到一个有序链表中得到。
1-> 1-> 2-> 3-> 4-> 4-> 5-> 6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 < = k < = 10^4
0 < = lists[i].length < = 500
-10^4 < = lists[i][j] < = 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

解题

fun _0023_mergeKLists()
println("--------_0023_mergeKLists-------")
mergeKLists(
arrayOf(
ListNode(1, ListNode(4, ListNode(5))),
ListNode(1, ListNode(3, ListNode(4))),
ListNode(2, ListNode(6)),
)
)?.print()
mergeKLists(arrayOf())?.print()

fun mergeKLists(lists: Array< ListNode?> ): ListNode?
val len = lists.size
if (len == 0) return null
else if (len == 1) return lists[0]
var min: ListNode? = null
val prev = ListNode(0)
var head: ListNode? = prev
while (true)
var id = -1
for (i in 0 until len)
if (min == null & & lists[i] != null)
min = lists[i]

val curr = lists[i]
if (curr != null & & curr.data < = min?.data!!)
min = curr
id = i

if (id != -1)
head?.next = min
head = head?.next
min = null
lists[id] = lists[id]?.next
else break

return prev.next

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 < = Node.val < = 100

解题

fun _0024_swapPairs()
println("--------_0024_swapPairs-------")
swapPairs(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))))?.print()
swapPairs(ListNode(1, ListNode(2, ListNode(3, ListNode(4)))))?.print()
swapPairs(ListNode(1, ListNode(2, ListNode(3))))?.print()
swapPairs(ListNode(1))?.print()

/**
* 利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换：
*/
fun swapPairs(head: ListNode?): ListNode?
if (head?.next == null)
return head

var temp = head.next
head.next = swapPairs(head.next?.next)
temp?.next = head
return temp

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1-> 2-> 3-> 4-> 5
当 k = 2 时，应当返回: 2-> 1-> 4-> 3-> 5
当 k = 3 时，应当返回: 3-> 2-> 1-> 4-> 5

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

解题

fun _0025_reverseKGroup()
println("--------_0025_reverseKGroup-------")
reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2)?.print()
reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 3)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
2
)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
3
)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
4
)?.print()

/**
* 首先遍历整个链表，统计出链表的长度，然后如果长度大于等于k，交换节点，当 k=2 时，每段只需要交换一次，
* 当 k=3 时，每段需要交换2此，所以i从1开始循环，注意交换一段后更新 pre 指针，然后 num 自减k，
* 直到 num< k 时循环结束
*/
fun reverseKGroup(head: ListNode?, k: Int): ListNode?
var dummy = ListNode(-1)
var pre: ListNode? = dummy
var cur: ListNode? = pre
dummy.next = head
var num = 0
while (cur?.next != null)
cur = cur.next
++num

while (num > = k)
cur = pre?.next
for (i in 1 until k)
var temp = cur?.next
cur?.next = temp?.next
temp?.next = pre?.next
pre?.next = temp

pre = cur
num -= k

return dummy.next