LeetCode 初级算法之链表,看看你都学会了吗?
theme: juejin highlight: xcode
本文正在参加「金石计划 . 瓜分6万现金大奖」
前言:最近自己也开始系统的刷面试题了,算法是过不去的坎,希望自己能够坚持下去✊,同行的朋友们共勉。
题一:删除链表中的节点
有一个单链表的 head,我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。
示例 1:
输入:head = [4,5,1,9], node = 5
输出:[4,1,9]
解释:指定链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9
解题思路:直接替换
此题考查了链表的结构, 我们在删除、添加元素时,只需要修改引用对象指针即可; - 删除:去除引用关系,让当前节点被下一个节点替代 - 添加:被某个位置的节点引用
由于这里传入被删除的该节点,所以使用下一个节点来替换被删除节点就可以了。
swift
func deleteNode(_ node: ListNode?, _ head: ListNode?) {
node?.val = node?.next?.val ?? 0
node?.next = node?.next?.next ?? nil
let head = head
}
题二:删除链表的倒数第N个节点
给你一个链表,删除链表的倒数第
n
个结点,并且返回链表的头结点。
示例 1:
输入: head = [1,2,3,4,5], n = 2
输出: [1,2,3,5]
解题思路:递归、双循环、快慢指针
这题同样在考查我们对链表的理解。
链表是线性数据结构,我们单从头节点中无法知道链表的长度。 通过遍历整个链表,我们才可以知道链表的长度。而确定了链表的长度之后,再去找到要被删除的元素就简单了。
递归
```swift func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? { let pos = length(head, n) if pos == n { return head?.next } return head }
func length(_ node: ListNode?, _ n: Int) -> Int { if node?.next == nil { return 1 } /// 获取前面一个节点 let pos = length(node?.next, n) + 1 if pos == n+1 { print("(pos)") node?.next = node?.next?.next } return pos } ```
双循环
第一次:确定链表长度 第二次:定位到n的位置,完成替换
```swift func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? { let pos = length(head, n) if pos == n { return head?.next } return head }
func length(_ node: ListNode?, _ n: Int) -> Int { if node?.next == nil { return 1 } /// 获取前面一个节点 let pos = length(node?.next, n) + 1 if pos == n+1 { print("(pos)") node?.next = node?.next?.next } return pos } ```
快慢指针
fast
、slow
两个指针,fast
先走n
次,然后和slow
一起移动。
slow
和fast
相距n
,
当fast
先走到链表底部,slow
就是要删除的对象;
swift
func removeNthFromEnd3(_ head: ListNode?, _ n: Int) -> ListNode? {
var fast = head
var slow = head
var index = n
/// jNode 移位 n
while index > 0 {
fast = fast?.next
index-=1
let j = fast
}
if fast?.next == nil { return head?.next }
/// 开始遍历
while fast?.next != nil {
fast = fast?.next
slow = slow?.next
}
slow?.next = slow?.next?.next
return head
}
题三:反转链表
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
示例 1:
输入: head = [1,2,3,4,5]
输出: [5,4,3,2,1]
解题思路:栈、递归、双指针
将单向链表翻转等于是改变链表方向;
栈操作
先进后出、后进先出。利用栈的特性,反转链表。 - 入栈:1 —> 2 —> 3 - 出栈:3 —> 2 —> 1
swift
func reverseList(_ head: ListNode?) -> ListNode? {
/// 全部入栈
var node = head
var stack = Stack<ListNode>()
while node != nil {
if let node = node {
stack.push(element: node)
}
node = node?.next
}
/// 第一个出栈的节点是新的表头
node = stack.pop()
/// 新的表头
var newHead = node
while !stack.isEmpty() {
let tempNode = stack.pop()
node?.next = tempNode
node = tempNode
}
node?.next = nil
return newHead
}
双指针
双指针:newHead
、node
\
每次循环,缓存node指针的下一个节点,这里比较关键。
然后
swift
func reverseList(_ head: ListNode?) -> ListNode? {
var node = head
var newhead: ListNode? = nil
while node != nil {
let temp = node?.next
node?.next = newhead
newhead = node
node = temp
}
return newhead
}
题四:合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入: l1 = [1,2,4], l2 = [1,3,4]
输出: [1,1,2,3,4,4]
解题思路:双指针
合并两个升序的链表其实和数组的思想类似。只是实现上有点区别。但是都可以使用双指针去实现。 两个指针分别指向两个链表的头部节点,比较两个节点的值大小,小的一方添加到链表中,并且把指针往后移。
swift
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
var node1 = list1
var node2 = list2
var newHead = ListNode(0)
var cur: ListNode? = newHead
while node1 != nil && node2 != nil {
let val1 = node1?.val ?? 0
let val2 = node2?.val ?? 0
if val1 <= val2 {
cur?.next = node1
node1 = node1?.next
} else {
cur?.next = node2
node2 = node2?.next
}
cur = cur?.next
}
cur?.next = node1 == nil ? node2 : node1
let head = newHead.next
return head
}
题五:回文链表
给你一个单链表的头节点
head
,请你判断该链表是否为回文链表。如果是,返回true
;否则,返回false
。
示例 1:
输入: head = [1,2,2,1]
输出: true
解题思路:栈操作、递归、反转后半链表
关键点就是对比首尾的各个节点;如何获取尾部的节点呢?答案是:栈操作、递归、反转后半链表。
递归也相当于栈操作
栈操作
先进后出、后进先出。
swift
func isPalindrome(_ head: ListNode?) -> Bool {
var node = head
var stack = Stack<Int>()
var length = 0
while node != nil {
if let node = node {
stack.push(element: node.val)
}
node = node?.next
length+=1
}
node = head
length/=2
while length > 0 {
if node?.val != stack.pop() {
return false
}
node = node?.next
length-=1
}
return true
}
反转后半链表
先找到中间链表 使用快慢指针 fast、slow (原理:fast+2,slow+1,fast到达终点,slow此时应该在中间)
判断奇偶数,如果fast不为空,则说明链表长度为奇数,若fast为空,则说明为偶数,找到中点,反转后半部分链表
判断反转后的链表是否和前半部分链表相同,如果全部相同则说明是回文链表,反之,则不是。
swift
func isPalindrome(_ head: ListNode?) -> Bool {
var fast = head
var slow = head
while fast != nil, fast?.next != nil {
fast = fast?.next?.next
slow = slow?.next
}
/// 奇数就选下一个
if fast != nil {
slow = slow?.next
}
var newNode = reverse(slow)
var node = head
while newNode != nil {
if newNode?.val != node?.val {
return false
}
newNode = newNode?.next
node = node?.next
}
return true
}
题六:环形链表
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回
true
。 否则,返回false
。
示例 1:
输入: head = [3,2,0,-4], pos = 1
输出: true
解释: 链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入: head = [1], pos = -1
输出: false
解释: 链表中没有环。
解题思路:集合法、快慢指针
集合法
如果不考虑内存问题,我们可以使用集合来缓存每次到访的节点。如果下一次命中缓存,则说明有环。
swift
func hasCycle(_ head: ListNode?) -> Bool {
var node = head?.next
var set = Set<ListNode>()
while node != nil {
if set.contains(node!) {
return true
} else {
set.insert(node!)
}
node = node?.next
}
return false
}
快慢指针
判断链表中有没有环,可以通过快慢指针来处理,
slow
走一步,fast
走两步,如果有环,当走到n次时,slow和fast相遇。 如果没有环,fast会先走到尾部,变为nil。
swift
func hasCycle(_ head: ListNode?) -> Bool {
var slow = head?.next
var fast = head?.next?.next
while fast != nil {
if slow === fast {
return true
}
slow = slow?.next
fast = fast?.next?.next
}
return false
}
小结
链表篇的初级算法看看你都学会了吗?链表的数据结构与数组的区别在于,数组在内存是连续的,而链表不需要连续。链表在插入和删除上也比较灵活,但是在查找时就比较麻烦,只能通过头节点一个个向后遍历查找。在很多链表的处理上,大多数都可以使用递归的方式。
链表:栈、递归、快慢指针、集合、双指针
- LeetCode 初级算法之数组(上),看看你都学会了吗?
- LeetCode 初级算法之链表,看看你都学会了吗?
- LeetCode 初级算法之字符串(上),看看你都学会了吗?
- 纯代码布局,也可以一样的简洁
- UIStackView之一问一答
- 使用UIStackView来简化iOS的界面布局
- 夏天来了,iOS开发者们该如何减少App耗电?(上)
- 夏天来了,App开发者们如何看待手机发烫问题?
- 聊聊iOS中UITableView复用的那些事
- 曾经经典的微信打飞机游戏还有人记得吗?
- iOS 原生渲染与 Flutter 有什么区别 (上)
- 了解 Mach-O文件
- CocoaPods中podsepc文件设置详解
- iOS 原生渲染与 Flutter 有什么区别 (下)
- 简单了解 iOS CVPixelBuffer (上)
- 谈谈 iOS 包瘦身方案
- 播放器重构的探索之路
- 如何使用CocoaPods制作私有库
- iOS 组件化方案