链表

应用场景

一个经典的链表应用场景，那就是 LRU（Least Recently Used，最近最少使用） 缓存淘汰算法。缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见:CPU缓存、数据库缓存、浏览器缓存等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留，由缓存淘汰策略来决定。常见的策略有三种：

• 先进先出策略 FIFO（First In，First Out）

• 最少使用策略 LFU（Least Frequently Used）

• 最近最少使用策略 LRU（Least Recently Used）

缓存就是利用了空间换时间的设计思想。如果把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。

• 对于执行较慢的程序，通过消耗更多的内存（空间换时间）来进行优化。

• 对于消耗过多内存的程序，通过消耗更多的时间（时间换空间）来降低内存的消耗。

实现LRU缓存淘汰算法

维护一个有序单链表，越靠近链表尾部的节点是越早之前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的节点，并将其从原来的位置删除，然后再插入到链表的头部

2. 如果此数据没有在缓存链表中，又可以分为两种情况：

   1. 如果此时缓存未满，则将此节点直接插入到链表的头部

   2. 如果此时缓存已满，则链表尾节点删除，将新的数据节点插入链表的头部

无论缓存是否满了，都需要遍历一遍链表，所以基于链表的实现思路，缓存访问的时间复杂度为O(n)。

继续优化，引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)。

示例代码

使用Go的标准库

import "container/list"

type elemVal struct {
    k, v int
}
type LRUCache struct {
    capacity int
    store    *list.List
    cache    map[int]*list.Element
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        capacity: capacity,
        store:    list.New(),
        cache:    map[int]*list.Element{},
    }
}

func (this *LRUCache) Get(key int) int {
    // 判断是否在cache中
    if _, ok := this.cache[key]; !ok {
        return -1
    }
    // 如果存在，将节点移动到链表头
    node := this.cache[key]
    this.store.MoveToFront(node)
    return node.Value.(elemVal).v
}

func (this *LRUCache) Put(key int, value int) {
    // 判断是否在cache中
    if _, ok := this.cache[key]; !ok {
        // 如果不在，插入数据
        node := elemVal{k: key, v: value}
        front := this.store.PushFront(node)
        this.cache[key] = front

        // 判断是否超过容量限制
        if this.store.Len() > this.capacity {
            back := this.store.Back()
            this.store.Remove(back)
            delete(this.cache, back.Value.(elemVal).k)
        }
    } else {
        // 如果存在，更新node的值并将节点移动到链表头
        node := this.cache[key]
        node.Value = elemVal{k: key, v: value}
        this.store.MoveToFront(node)
    }
}

自定义双链表

// 双链表中的节点
type DLNode struct {
    key, value int
    prev, next *DLNode
}

type LRUCache struct {
    size       int
    capacity   int
    cache      map[int]*DLNode
    head, tail *DLNode
}

func newDLNode(key, value int) *DLNode {
    return &DLNode{
        key:   key,
        value: value,
        prev:  nil,
        next:  nil,
    }
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{
        size:     0,
        capacity: capacity,
        cache:    make(map[int]*DLNode),
        head:     newDLNode(0, 0),
        tail:     newDLNode(0, 0),
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (this *LRUCache) addToHead(node *DLNode) {
    node.prev = this.head
    node.next = this.head.next

    this.head.next.prev = node
    this.head.next = node
}

func (this *LRUCache) removeNode(node *DLNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLNode) {
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLNode {
    node := this.tail.prev
    this.removeNode(node)
    return node
}

func (this *LRUCache) Get(key int) int {
    // 从哈希表中判断，不存在返回-1
    if _, ok := this.cache[key]; !ok {
        return -1
    }

    // 获取哈希表中存的节点
    node := this.cache[key]
    // 将该节点移动到链表头
    this.moveToHead(node)
    return node.value
}

// put新节点的时候，先将节点加入后再判断容量进行删除
func (this *LRUCache) Put(key int, value int) {
    // 从哈希表中判断
    if _, ok := this.cache[key]; !ok {
        //     如不存在，新建节点并添加到哈希表和链表头
        node := newDLNode(key, value)
        this.cache[key] = node
        this.addToHead(node)
        this.size++
        // 判断当前是否超过缓存容量
        if this.size > this.capacity {
            // 在链表和哈希表中删除最久未使用的
            removed := this.removeTail()
            delete(this.cache, removed.key)
            this.size--
        }
    } else {
        // 如果存在，直接更新节点中value的值
        node := this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}

链表结构

对比链表与数组的底层存储结构：

• 数组需要一块连续的内存空间来存储，对内存的要求比较高。如果申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。

• 链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。如果申请100MB大小的链表，根本不会有问题。

内存分布

链表结构五花八门，最常见的三种链表结构：单链表、双向链表和循环链表。

单链表

链表通过指针将一组零散的内存块串联在一起，其中的内存块称为链表的“节点”。

为了将所有的节点串起来，每个链表的节点除了存储数据之外，还需要记录链上的下一个节点的地址。如图所示，我们把这个记录下个节点地址的指针叫作后继指针next。

单链表

图中有两个节点是比较特殊的，它们分别是第一个节点（头节点）和最后一个节点（尾节点）。

• 头节点：用来记录链表的基地址。有了它，就可以遍历得到整条链表。

• 尾节点：指针不是指向下一个节点，而是指向一个空地址NULL，表示这是链表上最后一个节点。

与数组一样，链表也支持数据的查找、插入和删除操作。

在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。

在链表中插入或者删除一个数据，并不需要为了保持内存的连续性而搬移节点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的，只需要考虑相邻节点的指针改变，所以对应的时间复杂度是 O(1)。

插入和删除数据

链表要想随机访问第 k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个节点一个节点地依次遍历，直到找到相应的节点。所以，链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度。

循环链表

循环链表是一种特殊的单链表。与单链表唯一的区别就在尾节点。

• 单链表的尾节点指针指向空地址，表示这就是最后的节点了。

• 循环链表的尾节点指针是指向链表的头节点。它像一个环一样首尾相连，所以叫作“循环”链表。

循环链表

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表（如约瑟夫问题）。尽管用单链表也可以实现，但是用循环链表实现的话，代码就会简洁很多。

双向链表

• 单向链表只有一个方向，节点只有一个后继指针 next 指向后面的节点。

• 双向链表，支持两个方向，每个节点有一个后继指针 next 指向后面的节点，还有一个前驱指针 prev 指向前面的节点。

双向链表

从图中看出来，双向链表需要额外的两个空间来存储后继节点和前驱节点的地址。

• 如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。

• 两个指针比较浪费存储空间，但支持双向遍历操作更灵活。

从结构上来看，双向链表可以支持 O(1) 时间复杂度找到前驱节点，这使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

删除操作

在实际开发中，从链表中删除一个数据无外乎这两种情况：

1. 删除节点中“值等于某个给定值”的节点。

2. 删除给定指针指向的节点。

删除某个值对应的节点

不管是单链表还是双向链表，为了查找到值等于给定值的节点，都需要从头节点开始一个一个依次遍历对比，直到找到值等于给定值的节点，然后再通过指针操作将其删除。

删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的节点对应的链表操作的总时间复杂度为 O(n)。

删除某个指针对应的节点

已知要删除的节点的指针，但是删除某个节点 q 需要知道其前驱节点：

• 单链表并不支持直接获取前驱节点，所以，为了找到前驱节点，还是要从头节点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱节点，所以删除操作需要 O(n) 的时间复杂度。

• 双向链表中的节点已经保存了前驱节点的指针，不需要再遍历，所以删除操作只需要 O(1) 的时间复杂度。

同理在某个节点前插入节点也分两种情况，单链表时间复杂度O(n)，双链表时间复杂度O(1)。

对于有序链表，双向链表的按值查询的效率也要比单链表高。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。这也是用空间换时间的设计思想。

• 如果内存空间充足，更加追求代码的执行速度，可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。

• 如果内存比较紧缺，比如代码跑在手机或者单片机上，就要反过来用时间换空间的设计思路。

链表与数组性能比较

数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。

操作	数组	链表
插入删除	O(n)	O(1)
随机访问	O(1)	O(n)

数组和链表的对比，并不能局限于时间复杂度。在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

• 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。

• 链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

• 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。

• 链表本身没有大小的限制，天然地支持动态扩容，这也是它与数组最大的区别。

除此之外，如果代码对内存的使用非常苛刻，那数组就更适合你。

1. 因为链表中的每个节点都需要消耗额外的存储空间去存储一份指向下一个节点的指针，所以内存消耗会翻倍。

2. 而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的垃圾回收（Garbage Collection，GC）。

所以，在实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。

常考考点

删除排序链表中的重复元素

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

思路

因为链表已经有序，用一个指针从前往后遍历的过程中删除重复节点即可。

示例代码

func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil {
        // 可能存在多个连续重复的值
        // 用两重循环将当前节点与后续节点依次比较
        for cur.Next != nil && cur.Val == cur.Next.Val {
            cur.Next = cur.Next.Next
        }
        cur = cur.Next
    }
    return head
}

删除排序链表中的重复元素【变形1】

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

思路

需要将有重复值的节点都删除，第一个节点也可能被删除，所以需要在它之前增加一个dummy节点。

示例代码

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    // 第一个节点可能就是重复值的，需要使用卫戍节点
    dummy := &ListNode{Val: 0}
    dummy.Next = head
    cur = dummy

    var rmVal int
    for cur.Next != nil && cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val {
            rmVal = cur.Next.Val // 寻找到待删除的值
            for cur.Next != nil && cur.Next.Val == rmVal {
                // 从当前节点开始遍历并比较每个Val
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

反转链表

思路

使用三个指针，分别记录当前节点，前一个节点和下一个节点。

如果没有记录下一个节点的指针，那么在改变当前节点指针后，就与原链表断开了，无法继续走下去。

示例代码

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        // 记录下一个节点
        next := head.Next
        // 反转当前节点
        head.Next = pre
        // 移动到下一个节点
        pre = head
        head = next
    }
    return pre
}

翻转单链表【变体1】

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路

因为是链表的中间进行翻转，所以需要指针记录一个关键的位置：

• pre指针：记录翻转起始节点之前的节点，翻转结束后，pre指针的Next指向end指针

• head指针：记录翻转起始节点，也就是翻转部分新的尾节点

• cur指针：记录翻转终止节点后的一个节点，翻转结束，head指针的Next指向cur

• end指针：记录翻转部分当前节点的前一个节点，也就是翻转部分新的头节点

示例代码

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head==nil{
        return nil
    }

    // 可能从第一个节点开始，需要使用卫戍节点
    dummy := &ListNode{}
    dummy.Next = head

    var pre *ListNode // 记录反转前的那个节点
    head = dummy
    i := 0 // 记录当前遍历的节点位置，增加了卫戍节点，从0开始
    for i < m {
        pre = head
        head = head.Next
        i++
    }
    // 找到反转开始的节点
    // 此时pre记录的是反转前的那个节点
    // head记录的是反转开始的那个节点，也就是反转后的尾节点

    cur := head
    var end *ListNode // 记录反转结束的那个节点，也就是反转后的头结点
    for i <= n {
        next := cur.Next
        cur.Next = end

        end = cur
        cur = next
        i++
    }
    // 反转结束
    // 此时end是反转后的头结点
    // cur是反转结束的下一个节点

    pre.Next = end
    head.Next = cur

    return dummy.Next
}

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路

1. 新建一个头节点，作为结果链表的头节点

2. 因为两个链表已经有序，所以逐个比较节点的值，将较小值接入结果链表

示例代码

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    // 查看哪个链表还有剩下的节点直接接入
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return dummy.Next
}

分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。保留两个分区中每个节点的初始相对位置。

思路

两个链分别存储小于x和大于等于x的节点。

注意在拼接结果的时候，要把大于等于x的那个链表最后一个节点的Next指针设置为nil，否则会形成环。因为最后一个大于或等于X的节点可能不在原链表的末尾。

示例代码

func partition(head *ListNode, x int) *ListNode {
    if head == nil {
        return nil
    }

    dummy1 := &ListNode{}
    dummy2 := &ListNode{}
    cur1 := dummy1
    cur2 := dummy2

    for head != nil {
        if head.Val < x {
            cur1.Next = head
            cur1 = cur1.Next
        } else {
            cur2.Next = head
            cur2 = cur2.Next
        }
        head = head.Next
    }

    // 可能是节点中间的某个节点，需要把Next断开
    // 否则两个链拼接后，会形成环
    cur2.Next = nil
    cur1.Next = dummy2.Next
    return dummy1.Next
}

排序链表

在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序。

思路

需要在时间复杂度是O(nlogn)完成，且是原地排序，那么就是归并，快排，堆排序。

使用归并排序，关键就是找到链表的中点，将链表一分为二：

注意：在归并的过程中，需要将两个链表断开，middle.Next=nil

• 寻找链表中点的函数：使用快慢指针，分别从head.Next和head开始遍历，快指针为nil时，慢指针为中点

• 合并函数：将两个有序链表合并，实现方式与上面的合并两个有序链表相同

示例代码

func sortList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    return mergeSort(head)
}

func mergeSort(head *ListNode) *ListNode {
    // 递归退出条件，当前链表为空或者只剩下一个节点
    if head == nil || head.Next == nil {
        return head
    }

    middle := findMiddle(head)
    tail := middle.Next
    // 拆分为2个链表
    middle.Next = nil

    left := mergeSort(head)
    right := mergeSort(tail)

    return mergeTwoList(left, right)
}

func findMiddle(head *ListNode) *ListNode {
    // 此处fast=head.Next，这样得到的slow其实是中点的前一个点
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func mergeTwoList(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return dummy.Next
}

重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

思路

将链表拆分为前后两部分，然后交错的合并前后两部分。这里涉及的知识点很多：

• 寻找单链表中点：使用快慢指针

• 单链表翻转：使用pre、cur、next指针

• 交替合并两个链表：使用bool标志位来切换链表，最后要处理某个链表剩余的节点

示例代码

func reorderList(head *ListNode) {
    if head == nil {
        return
    }

    mid := findMiddle(head)
    tail := reverse(mid.Next)
    mid.Next = nil
    head = mergeTwo(head, tail)
}

func findMiddle(head *ListNode) *ListNode {
    // 此处fast=head.Next，这样得到的slow其实是中点的前一个点
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func reverse(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

func mergeTwo(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    head := dummy
    switcher := true

    for l1 != nil && l2 != nil {
        if switcher {
            head.Next = l1
            l1 = l1.Next
        } else {
            head.Next = l2
            l2 = l2.Next
        }
        head = head.Next
        switcher = !switcher
    }

    if l1 != nil {
        head.Next = l1
    }

    if l2 != nil {
        head.Next = l2
    }
    return dummy.Next
}

环形链表

给定一个链表，判断链表中是否有环。不存在一个节点指向自己的情况。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

思路

1. 使用一个指针开始遍历整个链表，不存在环则最后为nil，否则一直处于遍历状态，设置一个超时时间如100毫秒，超时未返回则存在环。

2. 使用一个哈希表存在遍历过的节点，每次遍历都比较一下是否已经遍历过该节点，遍历到nil则不存在环，否则存在环。

3. 使用快慢指针，如果两个指针相遇说明存在环。

示例代码

// 解法1
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    // 这个时间长度的设置是比较不好控制的
    after := time.After(time.Microsecond * 100)
    res := make(chan struct{})

    go func() {
        for head != nil {
            head = head.Next
        }
        res <- struct{}{}
    }()

    select {
    case <-res:
        return false
    case <-after:
        return true
    }
}

// 解法2
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    cache := make(map[*ListNode]bool)
    for head != nil {
        if cache[head] {
            return true
        }
        cache[head] = true
        head = head.Next
    }
    return false
}

// 解法3
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        if fast == slow {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

环形链表【变体1】

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

思路

1. 先判断链表是否有环

2. 存在环的情况下，当快慢指针相遇，将快指针回到链表头，快慢指针都以步长1运动，再次相遇时就是环入口

解释：

第一次相遇时，快指针比慢指针多绕环走了一圈，假设快指针运动了2k的距离，慢指针运动了k的距离，那么环的长度就是k。再假设入环点与相遇点的距离是x，那么从链表头到入环点的距离是k-x，从相遇的在继续运行k-x也刚好到入环点。

示例代码

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        if fast == slow {
            // 注意 fast指针指向head的同时slow要一起动一步
            fast = head
            slow = slow.Next
            // 继续往下走，直到再次相遇就是入环点
            for fast != slow {
                fast = fast.Next
                slow = slow.Next
            }
            return slow
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return nil
}

回文链表

请判断一个链表是否为回文链表。

思路

1. 找到链表中点

2. 断开链表

3. 翻转链表后半部分

4. 比较两个新链表中值是否一一对应

示例代码

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    mid := findMiddle(head)
    tail := reverse(mid.Next)
    mid.Next = nil

    for head != nil && tail != nil {
        if head.Val != tail.Val {
            return false
        }
        head = head.Next
        tail = tail.Next
    }
    return true
}

func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        // 此处fast=head.Next，这样得到的slow其实是中点的前一个点
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}


func reverse(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        next := head.Next
        head.Next = pre
        pre = head
        head = next
    }
    // 返回翻转后链表的最后一个节点作为新的头节点
    return pre
}