这是我的读书笔记总结,关于链表的一些详细知识点并不会展开说明,有不懂的地方可以自行查阅相关资料

1. 本节知识点

• 写好链表的一些技巧
• 链表的简单算法实现
• 基于链表实现LRU算法

2. 写好链表的一些技巧

0. 理解指针或引用的含义
1. 指针:将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量
2. 警惕指针丢失和内存泄露
3. 在添加节点或删除节点时,一定要注意顺序,否则会引起指针丢失
4. 利用哨兵(头节点)简化实现难度
5. 在操作链表时头部和尾部节点时,都需要特殊处理判断,如果使用哨兵节点,基本上可以避免上述操作
6. 重点留意边界条件处理
7. 举例说明,辅助思考
8. 多写多练,没有捷径

3. 链表的简单算法实现

说明: 以下的代码 都是基于Go语言实现的相关算法,完整代码会在文章末尾贴出!

0. 单链表反转

//定义节点
type Node struct {
	Value int
	Next  *Node
}
//定义链表
type LinkedList struct {
	Header *Node
}
//单链表反转
func (l *LinkedList) ReverseList(){
    var prev *Node //定义一个空节点
    curNode :=l.Header  //定义当前节点
    for curNode !=nil { //循环链表
        next :=curNode.Next  //定义下一个节点
        curNode.Next=prev //当前的下一个节点指向prev(反转)
        prev=curNode //更新prev 为当前节点
        curNode=next //更新当前节点为下一个节点
        
    }
    l.Header=prev  //将 Header节点更新为prev,没有这一步,反转后还是和以前一样,由于指针丢失,所以只会打印第一个值,不信你试试
    
}

看不懂?没关系

让我们通过一个具体的例子来说明这一点：

假设我们有一个链表 1 -> 2 -> 3 -> nil，现在我们要将它翻转。

初始时，prev 是 nil，current 是指向节点 1 的指针。

第一次迭代：

保存当前节点的下一个节点，即 next = 2。

将当前节点的 Next 指针指向 prev，即 1 -> nil。

更新 prev 为当前节点，即 prev = 1。

更新 current 为下一个节点，即 current = 2。

第二次迭代：

保存当前节点的下一个节点，即 next = 3。

将当前节点的 Next 指针指向 prev，即 2 -> 1。

更新 prev 为当前节点，即 prev = 2。

更新 current 为下一个节点，即 current = 3。

第三次迭代：

保存当前节点的下一个节点，即 next = nil（链表末尾）。

将当前节点的 Next 指针指向 prev，即 3 -> 2。

更新 prev 为当前节点，即 prev = 3。

更新 current 为下一个节点，即 current = nil。

循环结束，最终链表变为 3 -> 2 -> 1 -> nil。

通过将 prev 更新为当前节点，我们确保在下一次迭代时，能够正确地指向前一个节点，从而继续反转指向关系。这是链表翻转过程中的关键步骤之一

1. 链表中环的检测

//使用快慢指针来实现,慢指针有一步,快指针有2步,只要存在环,快指针会在某个时刻与慢指针重合,
// 如果不存在环,慢快指针会最先到达链表尾
func (l *LinkedList) HasCycle() bool {
    header :=l.Header
    //如果链表为空,则直接返回
    if header ==nil || header.Next==nil{
        return false
    }
    slow :=header
    fast :=header.Next
    for slow !=fast {
        if fast ==nil || fast.Next==nil{
            return false
        }
        slow=slow.Next
        fast=fast.next.next //快指针走2步
    }
}

2. 两个有序的链表合并

func (l *LinkedList) MerageTwoList(l1 *Node,l2 *Node){
    //定义头节点
    h := *Node{}
    //定义当前节点
    cur :=h
    for l1 !=nil && l2 !=nil{
        if l1.value<l2.value{
            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
    }
    h.Next=cur.Next //链表的头部
    
}

3. 删除链表倒数第 n 个结点

//最主要的问题,是如何定位到要删除的节点?
//利用快慢指针实现,先让快指针走n+1个位置,在同时移动快慢指针,
//直到快指针指向链表尾时,慢指针指向删除节点的前一位置
func (l *LinkedList) removeNthFromEnd(n int) {
    h :=l.Header
    slow :=h
    fast :=h
    //移动快指针对n+1处
    for i=0;i<=n;i++{
        fast=fast.Next
    }
    //同时移动快慢指针
    for fast !=nil{
        slow=slow.Next
        fast=fast.Next
    }
    //到这里 slow指针所在有位置是 删除节点的前一个位置
    slow.Next=slow.Next.Next
}

举个例子说明下:

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> 5，要删除倒数第 2 个节点（节点值为 4）。

首先，我们创建一个哑节点 dummy，并将其 Next 指向链表的头节点，以便处理边界情况。此时，链表变为：dummy -> 1 -> 2 -> 3 -> 4 -> 5。

接下来，我们需要让 fast 指针先向前移动 n+1 步。在这个例子中，n 是 2，所以 fast 先向前移动 3 步，到达节点 3。此时，fast 指针在节点 3，slow 指针在哑节点 dummy。

现在，我们让 slow 和 fast 指针同时向前移动，直到 fast 到达链表末尾。这是因为我们需要让 slow 指针停在要删除节点的前一个节点上。在这个例子中，fast 指针最终会到达节点 5，而 slow 指针会在节点 3 停下。

最后，我们将 slow 指针的 Next 指向倒数第 n+1 个节点的 Next，从而跳过了倒数第 n 个节点。在这个例子中，slow.Next 指向节点 5 的 Next，即节点 4 被删除。这样就完成了删除倒数第 2 个节点的操作。

删除后的链表：1 -> 2 -> 3 -> 5。

4. 基于链表实现LRU算法

说明:

这里使用双链表和hash表来实现,使用的库是container/list go内置库,对go不熟悉的同学,可以看看思路即可

 //定义LRU结构体
 //list.Element node节点
 type LRUCache struct {
     capacity int
     cache    map[int]*list.Element
     lruList  *list.List
 }
 //缓存的key value  这里只支持int类型 用在生产环境上,意义不大, 可以使用泛型来实现更完善的算法
 type CahceItem struct {
     key   int
     value int
 }
 //生成对象,就是初始化各个参数
 func NewLRUCache(n int) *LRUCache {
     return &LRUCache{
         capacity: n,
         cache:    make(map[int]*list.Element),
         lruList:  list.New(),
     }
 }
 //获取缓存中的值
 func (this *LRUCache) Get(key int) int {
     //判断key是否存在
     if e, ok := this.cache[key]; ok {
         //如里存在,则移动链表头部
         this.lruList.MoveToFront(e)
         //可以看做类型断言 如果为真,则返回转化后的值
         return e.Value.(*CahceItem).value
     }
     return -1
 }
 func (this *LRUCache) Set(key, value int) {
     if el, ok := this.cache[key]; ok {
         //如里存在,则更新对应的value,放到链表头部
         el.Value.(*CahceItem).value = value
         this.lruList.MoveToFront(el)
     } else {
         //不存在
         //判断是不是满了,如里满了就删除最后一位
         if len(this.cache) >= this.capacity {
             //取出最后一个元素
             lastEm := this.lruList.Back()
             //删除hash表中的数据
             delete(this.cache, lastEm.Value.(*CahceItem).key)
             //删除链表中的节点
             this.lruList.Remove(lastEm)
         }
         //放到链表头部
         newEl := this.lruList.PushFront(&CahceItem{key: key, value: value})
         //放入到hash表中
         this.cache[key] = newEl
     }
 }
 

5.完整的代码,如下 可运行

 
 package linkdemo
 
 import (
     "container/list"
     "fmt"
     "testing"
 )
 
 type Node struct {
     Value int
     Next  *Node
 }
 type LinkedList struct {
     Header *Node
 }
 
 // 添加链表
 func (l *LinkedList) AddNode(n int) {
     newNode := &Node{
         Value: n,
         Next:  nil,
     }
     if l.Header == nil {
         l.Header = newNode
     } else {
         curNode := l.Header
         for curNode.Next != nil {
             curNode = curNode.Next
         }
         //
         curNode.Next = newNode
     }
 
 }
 func (l *LinkedList) PrintList() {
     curNode := l.Header
     for curNode != nil {
         fmt.Println(curNode.Value, " ")
         curNode = curNode.Next
     }
 }
 
 // 翻转链表
 func (l *LinkedList) ReverseList() {
     var prev *Node
     curNode := l.Header
     for curNode != nil {
         next := curNode.Next //下个节点
         curNode.Next = prev  //将当前节点为的下一节点指向 prev
         prev = curNode       //更新prev 为当前节点
         curNode = next       //更新当前节点为下一个节点
 
     }
     l.Header = prev
 }
 
 // 检测链表中是否存在环
 func (l *LinkedList) HasCycle() bool {
     header := l.Header
     if header == nil || header.Next == nil {
         return false
     }
     slow := l.Header
     fast := l.Header.Next
     for slow != fast {
         if fast == nil || fast.Next == nil {
             return false
         }
         slow = slow.Next
         fast = fast.Next.Next
     }
     return true
 }
 func (l *LinkedList) MerageList(l1 *Node, l2 *Node) {
     h := &Node{} //定义头节点
     cur := h
     for l1 != nil && l2 != nil {
         if l1.Value <= l2.Value {
             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
     }
     l.Header = h.Next // 链表的头部
 }
 func (l *LinkedList) removeNthFromEnd(n int) {
     h := l.Header
     slow := h
     fast := h
     //先把快指针移动到要删除节点的前一位
     for i := 0; i <= n; i++ {
         fast = fast.Next
     }
     //同时移到快慢指针
     for fast != nil {
         slow = slow.Next
         fast = fast.Next
     }
     slow.Next = slow.Next.Next
 
 }
 func (l *LinkedList) findMiddleNode() *Node {
     slow, fast := l.Header, l.Header
     for fast != nil && fast.Next != nil {
         slow = slow.Next
         fast = fast.Next.Next
     }
     return slow
 }
 
 // 链表翻转
 func TestLinkReverse(t *testing.T) {
     list := LinkedList{}
     list.AddNode(1)
     list.AddNode(2)
     list.AddNode(3)
     list.AddNode(4)
     list.AddNode(5)
     list.PrintList()
     list.ReverseList()
     fmt.Println("---")
     list.PrintList()
 }
 func TestHasCycle(t *testing.T) {
     h := &LinkedList{}
 
     node1 := &Node{Value: 1}
     node2 := &Node{Value: 2}
     node3 := &Node{Value: 3}
     node4 := &Node{Value: 4}
     node5 := &Node{Value: 5}
     h.Header = node1
     node1.Next = node2
     node2.Next = node3
     node3.Next = node4
     node4.Next = node5
     //node5.Next = node2 //构造一个环
     hasCycle := h.HasCycle()
     if hasCycle == true {
         t.Error("存在环")
     } else {
         t.Error("不存在环")
     }
 }
 func TestMerageTwoLink(t *testing.T) {
     l1 := &Node{
         Value: 1,
         Next: &Node{
             Value: 3,
             Next: &Node{
                 Value: 5,
                 Next:  nil,
             },
         },
     }
     l2 := &Node{
         Value: 1,
         Next: &Node{
             Value: 3,
             Next: &Node{
                 Value: 4,
                 Next:  nil,
             },
         },
     }
     l := &LinkedList{}
     l.MerageList(l1, l2)
     l.PrintList()
 }
 func TestRemoveNthFromEnd(t *testing.T) {
     list := &LinkedList{}
     list.AddNode(1)
     list.AddNode(2)
     list.AddNode(3)
     list.AddNode(4)
     list.AddNode(5)
     list.PrintList()
     list.removeNthFromEnd(2)
     fmt.Println("=====")
     list.PrintList()
 }
 func TestFindMiddleNode(t *testing.T) {
     list := &LinkedList{}
     list.AddNode(1)
     list.AddNode(2)
     list.AddNode(3)
     list.AddNode(4)
     list.AddNode(5)
     list.AddNode(6)
     node := list.findMiddleNode()
     fmt.Println(node)
 }
 
 type LRUCache struct {
     capacity int
     cache    map[int]*list.Element
     lruList  *list.List
 }
 type CahceItem struct {
     key   int
     value int
 }
 
 func NewLRUCache(n int) *LRUCache {
     return &LRUCache{
         capacity: n,
         cache:    make(map[int]*list.Element),
         lruList:  list.New(),
     }
 }
 func (this *LRUCache) Get(key int) int {
     if e, ok := this.cache[key]; ok {
         //如里存在,则移动链表头部
         this.lruList.MoveToFront(e)
         return e.Value.(*CahceItem).value
     }
     return -1
 }
 func (this *LRUCache) Set(key, value int) {
     if el, ok := this.cache[key]; ok {
         //如里存在,则更新,放到链表头部
         el.Value.(*CahceItem).value = value
         this.lruList.MoveToFront(el)
     } else {
         //不存在
         //判断是不是满了,如里满了就删除最后一位
         if len(this.cache) >= this.capacity {
             lastEm := this.lruList.Back()
             delete(this.cache, lastEm.Value.(*CahceItem).key)
             this.lruList.Remove(lastEm)
         }
         newEl := this.lruList.PushFront(&CahceItem{key: key, value: value})
         this.cache[key] = newEl
     }
 }
 func TestLRU(t *testing.T) {
     cache := NewLRUCache(2)
     cache.Set(1, 1)
     cache.Set(2, 2)
     g := cache.Get(1)
     fmt.Println(g)
     cache.Set(3, 3)
     g2 := cache.Get(2)
     fmt.Println(g2)
 }