链表
链表相关的核心点
- null/nil 异常处理
- dummy node 哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
class Solution {
//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/solution/swift-bian-li-tong-shi-shan-chu-lian-biao-zhong-fu/
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
var current = head
while let now = current,let next = now.next{
if now.val == next.val {
now.next = next.next
}else{
current = now.next
}
}
return head
}
}
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现的数字。
思路:链表头结点可能被删除,所以用 dummy node 辅助删除
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
class Solution {
//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/swift-shuang-zhi-zhen-lian-biao-bian-li-tou-bu-tia/
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
let top = ListNode(0)
top.next = head
var prev = top
var current = head
while let now = current, var next = now.next {
if now.val == next.val{
//求出next指向最后一个相等的
while let end = next.next{
if now.val == end.val {
next = end
}else{
break
}
}
prev.next = next.next
current = next.next
}else{
prev = now
current = next
}
}
return top.next
}
//递归实现
//https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/swift-di-gui-shi-xian-by-hu-cheng-he-da-bai-sha/
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
var res = head
if let current = res,let next = current.next{
if current.val == next.val{
var end : ListNode? = next
while end != nil && current.val == end!.val {
end = end!.next
}
res = deleteDuplicates(end)
}else{
current.next = deleteDuplicates(next)
}
}
return res
}
}
注意点 • A->B->C 删除 B,A.next = C • 删除用一个 Dummy Node 节点辅助(允许头节点可变) • 访问 X.next 、X.value 一定要保证 X != nil
反转一个单链表。
思路:用一个 prev 节点保存向前指针,temp 保存向后的临时指针
//https://leetcode-cn.com/problems/reverse-linked-list/solution/swift-shuang-zhi-zhen-bian-li-by-hu-cheng-he-da-ba/
//双指针遍历
//执行用时:20 ms, 在所有 Swift 提交中击败了78.48%的用户
//内存消耗:21.7 MB, 在所有 Swift 提交中击败了25.00%的用户
func reverseList_a(_ head: ListNode?) -> ListNode? {
var head = head
var prev: ListNode?
while let current = head {
let next = current.next
current.next = prev
prev = head
head = next
}
return prev
}
//https://leetcode-cn.com/problems/reverse-linked-list/solution/swift-gao-xiao-di-gui-by-hu-cheng-he-da-bai-sha/
//递归
//执行用时:16 ms, 在所有 Swift 提交中击败了97.24%的用户
//内存消耗:22.1 MB, 在所有 Swift 提交中击败了25.00%的用户
func reverseList(_ head: ListNode?) -> ListNode? {
guard let current = head,let next = current.next else {
return head
}
let reverse = reverseList(next)
next.next = current
current.next = nil
return reverse
}
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路:先遍历到 m 处,翻转,再拼接后续,注意指针处理
//https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/swift-bian-li-fan-zhuan-by-hu-cheng-he-da-bai-sha/
//遍历反转
//执行用时:12 ms, 在所有 Swift 提交中击败了38.37%的用户
//内存消耗:20.9 MB, 在所有 Swift 提交中击败了100.00%的用户
func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
let sentry = ListNode(0)
sentry.next = head
var prev: ListNode? = sentry
var cur: ListNode? = head
//移动到反转起始位置
for _ in 1..<m{
prev = cur
cur = cur?.next
}
let beign = prev//记录反转第一个的前一个
let end = cur//记录反转的第一个
//反转m到n个元素
for _ in m...n {
let next = cur?.next
cur?.next = prev
prev = cur
cur = next
}
beign?.next = prev//重新标记反转后的头
end?.next = cur//重新标记反转后的尾
return sentry.next
}
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:通过 dummy node 链表,连接各个元素
//https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/swift-di-gui-by-hu-cheng-he-da-bai-sha/
//递归实现
//执行用时:16 ms, 在所有 Swift 提交中击败了94.75%的用户
//内存消耗:21.1 MB, 在所有 Swift 提交中击败了100.00%的用户
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let res = ListNode()
guard let cur1 = l1 else {
return l2
}
guard let cur2 = l2 else {
return l1
}
if cur1.val < cur2.val {
res.next = cur1
let next = mergeTwoLists(cur1.next,cur2)
cur1.next = next
}else{
res.next = cur2
let next = mergeTwoLists(cur1,cur2.next)
cur2.next = next
}
return res.next
}
//https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/swift-die-dai-by-hu-cheng-he-da-bai-sha/
//迭代
//执行用时:16 ms, 在所有 Swift 提交中击败了94.75%的用户
//内存消耗:20.8 MB, 在所有 Swift 提交中击败了100.00%的用户
func mergeTwoLists_a(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = l1, l2 = l2
let res = ListNode()
var current = res
while let cur1 = l1, let cur2 = l2 {
if cur1.val < cur2.val{
current.next = cur1
l1 = cur1.next
}else{
current.next = cur2
l2 = cur2.next
}
current = current.next!
}
current.next = l1 ?? l2
return res.next
}
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。