Swift ～ 链表小结
2019-02-14 本文已影响22人
派大星的博客
1、链表数据结构
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}
2、 根据给定数组生成一个链表
func createList(_ array: [Int]) -> ListNode? {
let head: ListNode? = ListNode(-1)
var ref: ListNode? = head
for item in array {
let listItem = ListNode(item)
ref?.next = listItem
ref = ref?.next
}
return head?.next
}
3、插入节点
// 插入尾节点
func addToTail(_ head: ListNode?, val: Int) -> ListNode? {
let item = ListNode(val)
if head == nil {
return item
} else {
var ref = head
while ref?.next != nil {
ref = ref?.next
}
ref?.next = item
return head
}
}
// 插入头节点
func addToFront(_ head: ListNode?, val: Int) -> ListNode? {
let item = ListNode(val)
item.next = head
return item
}
4、删除第一个val节点
// 因为头结点有可能被删除，此时我们用一个headPre指向当前的头节点，进行遍历。
func removeNode(_ head: ListNode?, val: Int) -> ListNode? {
let headPre : ListNode? = ListNode(-1)
headPre?.next = head
var ref = headPre
while (ref?.next != nil) {
if (ref?.next?.val == val) {
ref?.next = ref?.next?.next
break
}
ref = ref?.next
}
return headPre?.next
}
5、删除所有val节点
// Remove all elements from a linked list of integers that have value val.
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
let headPre : ListNode? = ListNode(val)
headPre?.next = head
var ref = headPre
while (ref?.next != nil) {
if (ref?.next?.val == val) {
ref?.next = ref?.next?.next
} else {
ref = ref?.next
}
}
return headPre?.next
}
// 官方优秀实现
func removeElements2(_ head: ListNode?, _ val: Int) -> ListNode? {
guard head != nil else { return nil }
var head = head
while head != nil, head!.val == val {
head = head?.next
}
var prev = head
var current = head?.next
while let curr = current {
if curr.val == val {
prev?.next = curr.next
current = curr.next
continue
}
prev = curr
current = curr.next
}
return head
}
6、找到中间节点
func middleNode(_ head: ListNode?) -> ListNode? {
var p1 = head
var p2 = head
while p2?.next != nil {
p1 = p1?.next
p2 = p2?.next?.next
}
return p1
}
7、反转链表
我的简易理解：逐个遍历原链表节点，利用插入头指针的方法生成逆序的新链表。
func reverseList(_ head: ListNode?) -> ListNode? {
var rList : ListNode? = nil
var lList = head
var tmp : ListNode? = nil
while lList != nil {
tmp = lList
lList = lList?.next
tmp?.next = rList
rList = tmp
}
return rList
}
// 官方优秀递归实现
func reverseListRecursively(_ head: ListNode?) -> ListNode? {
if let head = head {
if let next = head.next {
let newHead = reverseList(next)
next.next = head
head.next = nil
return newHead
}
}
return head
}
8、合并两个有序链表
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let headPre : ListNode? = ListNode(-1)
var ref = headPre
var l = l1
var r = l2
while (l != nil && r != nil) {
if l!.val <= r!.val {
ref?.next = l
ref = ref?.next
l = l?.next
} else {
ref?.next = r
ref = ref?.next
r = r?.next
}
}
if l == nil {
ref?.next = r
} else {
ref?.next = l
}
return headPre?.next
}
// 官方优秀递归实现
func mergeTwoListsRecursively(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
if l1 == nil {
return l2
}
if l2 == nil{
return l1
}
if let first = l1, let second = l2{
if first.val < second.val{
first.next = mergeTwoLists(first.next, second)
return first
} else {
second.next = mergeTwoLists(first, second.next)
return second
}
}
return nil
}
9、请检查一个链表是否为回文链表
进阶：你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？
思路：链表用到了快慢指针，快指针每次跳两下，慢指针每次跳一下，这样快指针到终点的时候慢指针刚好一般，然后反转后半部分链表进行对比。 该方法时间复杂度O(n)、空间复杂度O(1).
func isPalindrome(_ head: ListNode?) -> Bool {
let middle = self.middleNode(head)
let reverse = self.reverseList(middle)
var r = reverse
var l = head
while r != nil {
if r?.val != l?.val {
return false
}
r = r?.next
l = l?.next
}
return true
}
10、给定一个链表，去除重复的元素，使每个元素最多出现一次
Remove Duplicates from Sorted List
给定一个链表，去除重复的元素，使每个元素最多出现一次。
例如：给定 1->1->2, 返回 1->2.
给定 1->1->2->3->3, 返回 1->2->3.
func deleteDuplicate(_ head: ListNode?) -> ListNode? {
var tmp = head
while tmp != nil {
if tmp?.next?.val == tmp?.val {
tmp?.next = tmp?.next?.next
} else {
tmp = tmp?.next
}
}
return head
}
11、给定一个链表，要求删除重复的元素，只保留单独的元素
Remove Duplicates from Sorted List II
给定一个链表，要求删除重复的元素，只保留单独的元素。
例如：给定 1->2->3->3->4->4->5, 返回 1->2->5.
给定 1->1->1->2->3, 返回 2->3.
便利提示：因为头结点有可能被删除，此时我们用一个headPre指向当前的头节点，进行遍历。
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
let headPre : ListNode? = ListNode(-1)
headPre?.next = head
var ref = headPre
while (ref?.next != nil && ref?.next?.next != nil){
if (ref?.next?.val == ref?.next?.next?.val) {
let value = ref?.next?.val
while(ref?.next != nil && ref?.next?.val == value) {
ref?.next = ref?.next?.next
}
} else {
ref = ref?.next
}
}
return headPre?.next
}
// 官方优秀实现
func deleteDuplicatesLeetcode(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil { return head }
let dummy = ListNode(0)
var node: ListNode? = dummy
var slow = head
var fast = head?.next
var dupli = false
while fast != nil {
if fast!.val == slow!.val {
dupli = true
} else {
if !dupli {
node?.next = slow
node = slow
}
dupli = false
}
slow = fast
fast = fast?.next
}
if !dupli {
node?.next = slow
node = slow
}
node?.next = nil
return dummy.next
}
