恋上数据结构与算法二（数组链表）

数据结构：计算机存储、组织数据的方式

线性表

具有n个相同类型元素的有限序列（n>=0）

屏幕快照 2020-07-07 下午6.26.28.png

a1是首节点（首元素），an是尾节点（尾元素）
a1是a2的前驱，a2是a1的后继

常见的线性表有：数组、链表、栈、队列、哈希表（散列表）

数组

数组是一种顺序存储的线性表，所有元素的内存地址是连续的
动态数组可能会造成内存空间的大量浪费

链表

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表可以用多少就申请多少内存，每当添加新的元素就分配存储空间

屏幕快照 2020-07-08 上午11.12.26.png

public class ListNode {
     public var val: Int
     public var next: ListNode?
     public init(_ val: Int) {
        self.val = val
         self.next = nil
     }
}
class List {
    var head: ListNode?
    var tail: ListNode?
    var isEmpty: Bool {
        return head == nil
    }
    //头插法
    func appendToTail(val: Int) {
        let node = ListNode(val)
        if tail == nil {
            tail = node
            head = tail
        } else {
            tail?.next = node
            tail = tail?.next
        }
    }
    //尾插法
    func appendToHead(val: Int) {
        let node = ListNode(val)
        if head == nil {
            head = node
            tail = head
        } else {
            node.next = head
            head = node
        }
    }
}

双向链表

//链表结点
class Node<T> {
    var value: T
    var next: Node<T>?
    weak var prev: Node<T>?
    init(value: T, next: Node<T>? = nil) {
        self.value = value
    }
}

循环链表

练习

1. 删除链表中一个结点

2. 反转链表

递归法
反转 n1->n2->...->nm，相当于反转 n1->(nil<-n2<-...<-nm)

屏幕快照 2020-07-09 上午10.43.26.png

func reverseList(_ head: ListNode?) -> ListNode? {
       if head == nil || head?.next == nil {
            return head
        }

        let newhead = reverseList(head?.next)
        let next = head?.next //4
        next?.next = head
        head?.next = nil
        return newhead
    }

迭代法
用一个变量保存上一个结点
依次遍历结点，将结点next指向上一个结点

func reverseList(_ head: ListNode?) -> ListNode? {
        //上一个结点
        var pre: ListNode?
        //当前遍历的结点
        var cur = head
        while cur != nil {
            let next = cur?.next
            cur!.next = pre
            //当前结点往后移
            pre = cur
            cur = next
        }
        return pre
}

定义一个新的头结点指针指向 NHead->NULL
定义临时变量p指针遍历原来链表
遍历p->1 NHead->1->NULL
p移动到2 p->2 NHead->2->1->NULL
直到p指针遍历到NULL

3. 判断一个链表是否有环

快慢指针
快指针走两步，慢指针走一步
如果有环，快慢指针一定会相遇
如果没环，快指针先指向空nil

屏幕快照 2020-07-09 下午2.48.24.png

func hasCycle(_ head: ListNode?) -> Bool {
    if head == nil || head?.next == nil { return false }
        var slow = head
        var fast = head?.next
        
        while fast != nil {
            if slow === fast { return true }
            slow = slow?.next
            fast = fast?.next?.next
        }
        return false
}

4.移除链表元素

删除链表中等于给定值 val 的所有节点
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    //记录上一个结点
    var pre: ListNode?
    //记录遍历的结点
    var cur = head
    //新的头结点
    var head: ListNode?
    while cur != nil {
        if cur?.val == val {
            //移除当前结点
            pre?.next = cur?.next
        } else {
            if head == nil {
                head = cur
            }
            pre = cur
        }
        //下移
        cur = cur?.next
    }
    return head
}
//递归方式
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    if head == nil {
        return nil
    }
    head?.next = removeElements(head?.next, val)
    return (head?.val ?? 0) == val ? head?.next : head
}

5. 删除链表中重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次

//递归
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
    if head == nil {
        return nil
    }
   head?.next = deleteDuplicates(head?.next)
    return (head?.val == head?.next?.val) ? head?.next : head
}

6.删除链表中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点
如果有两个中间结点，则返回第二个中间结点

//快慢指针 快指针到末尾时 慢指针位于中间
func middleNode(_ head: ListNode?) -> ListNode? {
     var slow = head
     var fast = head
     while fast != nil && fast?.next != nil {
          slow = slow?.next
          fast = fast?.next?.next
    }
    return slow
}

数据结构与算法动态可视化