链表

在计算机科学中，链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
维基百科

优缺点

  • 数组:

优点：使用方便 ，查询效率 比链表高，内存为一连续的区域
缺点：大小固定，不适合动态存储，不方便动态添加

  • 链表:

优点：可动态添加删除,大小可变,添加删除不需要像数组那样向前后移动数组
缺点：只能通过顺次指针访问，查询效率低

Swift实现

class ListNode {
    var value: Int
    var next: ListNode?
    
    init(value: Int) {
        self.value = value
        self.next = nil
    }
}

class List {
    var head: ListNode?
    var tail: ListNode?
    
    @discardableResult func appendToTail(_ value: Int) -> ListNode? {
        if tail == nil {
            tail = ListNode(value: value)
            head = tail
        } else {
            tail?.next = ListNode(value: value)
            tail = tail?.next
        }
        return tail
    }
    
    func appendToHead(_ value: Int) {
        if head == nil {
            head = ListNode(value: value)
            tail = head
        } else {
            let temp = ListNode(value: value)
            temp.next = head
            head = temp
        }
    }
}

链表的结构非常简单，所以也没有太多可以说的。

算法题

给一个链表和一个值x，要求将链表中所有小于x的值放到左边，所有大于等于x的值放到右边。
例：1->5->3->2->4->2，给定x = 3。则我们要返回 1->2->2->5->3->4

基本思路就是引入两个dummy节点，然后遍历原链表，将大于和小于3的分别"串"在两个空节点上，最后将两个dummy节点连在一起就ok了。

func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
    var prev = ListNode(value: 0)
    var prevDummy = prev
    
    let post = ListNode(value: 0)
    var postDummy = post
    
    var node: ListNode? = head
    
    repeat {
        if node!.value < 3 {
            prevDummy.next = node
            prevDummy = node!
            print("****",node?.value,
                  node?.next?.value,
                  prevDummy.value,
                  prevDummy.next?.value,
                  prev.value)
        } else {
            postDummy.next = node
            postDummy = node!
        }
        node = node?.next
    } while(node != nil)
    
    postDummy.next = nil
    prevDummy.next = post.next
    print("------", prev.value)
    return prev.next
}

通过算法我们可以看出，最开始的Prev和Post节点很重要，假设没有的话，那在你将两个链表排序后，你的当前指针是指向尾部的，那我们这道题是单向链表，是无法返回去找到头结点了。所以最开始的prev和post就很好地解决了这个问题。在链表的使用中，这种“记录头节点”的方式很实用。

如何检测链表中是否有环

// 1 -> 2 -> 3 -|
//           |  4
//        -> 7  |
//       | 6 <- 5

类似此种结构

这就要用到快行指针的方式来解决此类问题。简单的说就是两个指针，一个在链表上移动的慢，一个运动的快，如果他们相遇了，那说明有环。

let cyclist = List()
cyclist.appendToTail(1)
cyclist.appendToTail(2)
let node3 = cyclist.appendToTail(3)
cyclist.appendToTail(4)
cyclist.appendToTail(5)
cyclist.appendToTail(6)
let tailNode = cyclist.appendToTail(7)

tailNode?.next = cyclist.head


func hasCycle(_ head: ListNode?) -> Bool {
    var slowPointer = head
    var fastPointer = head
    
    while fastPointer != nil {
        print("慢: ",slowPointer?.value ?? "", "快", fastPointer?.value ?? "")
        slowPointer = slowPointer?.next
        fastPointer = fastPointer?.next?.next
        
        if slowPointer === fastPointer {
            print("慢: ",slowPointer?.value ?? "", "快", fastPointer?.value ?? "")
            return true
        }
    }
    
    return false
}

从上面的算法，我们就能看出来，慢指针移动一个单位，快指针移动两个单位。如果他们在某次移动中指向同一个节点，那么说明有环。

删除倒数第n个节点

let removelist = List()
removelist.appendToTail(1)
removelist.appendToTail(2)
removelist.appendToTail(3)
removelist.appendToTail(4)
removelist.appendToTail(5)

func removeNthFromEnd(head: ListNode?, n: Int) -> ListNode? {
    let dummyNode = head
    var prevNode: ListNode? = head
    var postNode: ListNode? = head
    
    
    for _ in 0 ..< n {
        if postNode != nil {
            postNode = postNode?.next
        } else {
            fatalError("n must <= List's length")
        }
    }
    
    print("快指针的起始位置:", postNode?.value ?? "")
    
    while postNode?.next != nil {
        prevNode = prevNode?.next
        postNode = postNode?.next
        print("慢指针移动带:", prevNode?.value ?? "", "快指针移动到:", postNode?.value ?? "")
    }
    
    print("找到后慢指针的位置：", prevNode?.value ?? "", "找到后快指针的位置：", postNode?.value ?? "")
    
    prevNode?.next = prevNode?.next?.next
    
    return dummyNode
}

思路是一样的，只是初始状态下，快指针的位置的问题。

关于快行指针的数学抽象

这是我在做上面判断链表是否有环的时候思考的问题。
为什么快的指针一定会追上慢的指针？如何用数学来证明。
或者说能不能抽象出一个数学公式，根据三个已知条件
1直接给出 n个节点的环
2快慢指针的步幅
3起始距离
直接算出几步能确定有环

想用数学的形式证明，那就得是“老”套路，从特殊到一般呗。
那最特殊的，也是最简单的就是慢指针每次移动一，快指针每次移动二。
因为每次移动，快指针都向慢指针更近一个单位 所以快指针和慢指针的初始距离，就是需要几次移动，两个指针在相同的节点。

比如 ：

1->2->3 -v
|        |      
0<-6<-5<-4

一个0到6首尾相连的环，慢指针在4，快指针在2

  1. 慢5 快4
  2. 慢6 快6

4 - 2 = 2 两步“追上”
慢指针在2，快指针在4

  1. 慢3 快6
  2. 慢4 快1
  3. 慢5 快3
  4. 慢6 快5
  5. 慢0 快0

其实也是一样的，每次移动，快指针就都向慢指针更近一个单位，那想现在他们的距离是5 6 0 1 2，五个单位，所以就是5步。

不要被题中的 1 2 3 4误解，认为谁的“数字”大，谁就靠前，要知道在一个圆环上，你认为谁在“前面”，谁就在“前面”，1 2 3 4 只不过是标记的“位置”而已。所以无论它俩在哪个位置上，我们总是认为是快指针在“追击”慢指针。

你也可以用7进制来理解这个问题。
1 2 3 4 5 6 10 11 12 13 14，因为我们总是认为慢指针在“前”，所以我们可以认为慢指针现在在12的位置上，而快指针在4。那在6进制面前，12 - 4 = 5。

这其实不是一个严谨的数学证明，但也是可以“推”出在慢指针每次一个单位，快指针每次2个单位的情况下，如果存在换，是一定可以找到的。

然后我们再来看慢指针每次1个单位，快指针每次3个单位的情况。

我们假设链表长度为n,且顺序增长 🌰： 0 1 2 3 4 5 6
那么 慢指针第x次移动后。会在链表的 x%n位置，比如 移动7次，那x%7 = 0，慢指针会在0的位置上。

那快指针呢？每次移动3个单位。所以它的路线是 0 3 6 2 5 1 4，所以它的数学抽象表达应该是 3n%7比如 移动 8次 24%7 = 3，快指针就在第3个位置上
那么 求出几步相遇就是 x%n = 3x%n 我们可以看出当x是n的倍数的时候，一定有整数解且为0，因为我们在本次讨论中，默认都是从0位置出发的。所以假设n为7，那下一次相遇，就是第 7 14 21步。
那在通用一些，如果慢指针在快指针前 s 个单位呢？
则有 (x+s)%n = 3x%n
假设， n为7 s为3 (x+3)%7 = 3x%7
其实可以猜出来x为5 8%7 = 15%7 没问题。
不过我们只是试出了结果的正确性，但没有推导出来。后续还有很大的讨论空间。
未完待续。。。

参考资料：
Swift算法实战之路：链表
书籍：
《数据结构（C语言版）》



« 二叉树
Hash表 »

Copyright © 2015 Powered by MWeb,  Theme used GitHub CSS.

TOP