【数据结构+算法】——搞定链表

「爱情、让人受尽委屈。」 2022-12-24 14:51 103阅读 0赞

之前反复介绍过链表的概念，写这篇文章的目的是为了打破在日常学习中对链表一看就会，一写就废的困境，希望能真正搞懂链表，然后以此为根基学习更多的内容。  
**进阶参考资料：**  
极客时间《数据结构与算法之美》——王争  
极客算法训练营—— 覃超  
LeetCode网站

--------------------

### 链表 ###

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域,也称为后继指针next。  
![在这里插入图片描述][20201128213005440.png]  
链表中有两个结点比较特殊，分别为第一个结点（头节点）和最后一个节点（尾结点）。头节点记录了链表的基地址。有它可以变量整个链表，而尾结点当指针不是指向下一个节点，而是指向空地址NULL，则表示为链表上最后一个结点。  
上述讲解为基础的单链表，再次基础上扩展循环链表和双向链表。  
**循环链表**是一种特殊的单链表，它与单链表唯一的区别在于尾结点，循环链表的尾结点是指向链表的头节点。  
![在这里插入图片描述][20201128213722198.png]  
**双向链表**为了解决单链表只有一个方向的不足，它支持两个方向，除了后继指针next还有前驱指针prev指向前面结点。  
![在这里插入图片描述][20201128213925820.png]

#### 链表作用 ####

缓存，缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？涉及淘汰策略，常见三种策略：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。  
散列表, 本质上也链表和数组的结合体  
LinkedList，双向链表

#### 链表基本使用 ####

public class ListNode { 
        int val;
        ListNode next;
    
        ListNode(int x) { 
            val = x;
        }
    
        public static void main(String[] args) { 
            ListNode node = new ListNode(-1);
            //逻辑的关键 addNode 本质上不代表node，只是node的next的指针指向的空间地址
            ListNode addNode = node;
            for (int i = 0; i < 3; i++) { 
                //新增元素
                addNode.next = new ListNode(i);
                addNode = addNode.next;
            }
            //递归遍历列表，获取链表中数据详情
            getNodeVal(node);
            // 删除元素
            node.next = node.next.next;
            System.out.println("————————删除元素后————————");
            getNodeVal(node);
        }
    
        public static void getNodeVal(ListNode node) { 
            if (node == null) { 
                System.out.println();
                return;
            } else { 
                System.out.print(node.val + "|");
                getNodeVal(node.next);
            }
    
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70]  
为了避免一看就会一写就废的怪圈，建议大家手写下，感受下我代码中注释

--------------------

### 链表技巧 ###

1.  理解指针或引用的含义
2.  警惕指针丢失和内存泄漏
3.  利用哨兵简化实现难度  
    head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。  
    采用哨兵到底如何好处呢？
    
        //未采用哨兵
          ListNode node = null;
          int val = 1;
          if (node == null) { 
              node = new ListNode(val);
          } else { 
              node.next = new ListNode(val);
              node = node.next;
          }
          //打印node中元素内容
          getNodeVal(node);
          
          //采用哨兵
          ListNode temp = new ListNode(-1);
          int tempVal = 2;
          temp.next = new ListNode(tempVal);
          getNodeVal(temp.next);
    
    如果没有这个带头的哨兵，涉及到ListNode的编辑操作都要涉及到判空，但是如果有哨兵的模式，则接下来的逻辑处理变简单了很多，从效率上来说，也是空间换时间的最佳操作。
4.  重点留意边界条件处理
    
     *  单元测试也是这样验证的
     *  如果链表为空时，代码是否能正常工作？
     *  如果链表只包含一个结点时，代码是否能正常工作？
     *  如果链表只包含两个结点时，代码是否能正常工作？
     *  代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
5.  举例画图，辅助思考
6.  多写多练，没有捷径

--------------------

### LeetCode练习题 ###

练熟以下几题，不再恐惧写链表的操作  
206-单链表反转  
21-两个有序的链表合并  
141-链表中环的检测  
19-删除链表倒数第 n 个结点  
876-求链表的中间结点  
做题方式请看[《【数据结构+算法】——概览篇》][Link 1]，千言万语都抵不过脚踏实地，动手敲敲，相信一定有惊喜。

--------------------

### 链表两种思路 ###

当我们真正的去把上边几个去实现，里面还是有很强的方法性，也开始理解数据结构和算法重点不是刷过多少题目，而且要去理解思维方式。其实本质上有三种思路，1迭代，2递归，3双指针。迭代的本质偏向于暴露破解，如果从时间复杂度上来说，还是建议需要多加考虑。主要讲解另外两种方式。

#### 递归 ####

构成递归需具备的条件：

1.  子问题须与原始问题为同样的事，且更为简单；
2.  不能无限制地调用本身，须有个出口，化简为非递归状况处理。

结合链表，每个结点都是独立个体，而且出口条件非常明显，则是当next后继指针指向null，则链表终止  
所以在涉及到需要遍历链表的场景中，结合递归均可实现，例如上述联系题目中206-链表反转，21-两个有序的链表合并，也可以说通常在链表使用迭代能完成的事情，使用递归也基本可以。

#### 双指针 ####

无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。而我们遇到场景却都是删除倒数第n个元素，检查链表中是否存在环，求链表中间节点，这些巧好都和链表长度有关系，而这些问题都可以使用双指针来解决。  
**双指针不是固定的公式，而是一种思维方式。**  
例如删除倒数第n个元素，设有两个指针p和q,初始位均指向头结点，首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70 1]

public ListNode removeNthFromEnd(ListNode head, int n) { 
            if(head ==null || n ==0){ 
                return head;
            }
            ListNode fast = head;
            while(n!=0){ 
                if(fast==null){ 
                    return head;
                }
                fast = fast.next;
                n--;
            }
            ListNode newNode = new ListNode(0,head);
            ListNode slow = newNode;
            while(fast!=null){ 
                fast = fast.next;
                slow = slow.next;
            }
            slow.next = slow.next.next;
            return newNode.next;
      }

获取链表的中间结点。同样设置两个指针slow和fast，初始指向头节点，每次移动，fast向后走两次，slow向后走一次，直到fast无法向后移动两次。每次移动，fast和slow中距离就会增加一。所以当存在n个元素，则最多移动n/2轮。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70 2]

public ListNode middleNode(ListNode head) { 
            if(head==null || head.next==null){ 
                return head;
            }
            ListNode slow = head;
            ListNode fast = head;
            while(fast!=null){ 
                fast = fast.next;
                if(fast== null){ 
                    return slow;
                }
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

关于递归和双指针推荐leetcode中两篇解题思路  
[一文搞定常见的链表问题][Link 2]  
[快慢指针（注意链表长度为偶数时，返回第 2 个结点的细节）  
][2 _]

--------------------

### 总结 ###

小编主要写了写链表的两种思维，以及写链表的6个技巧。随着对链表的练习则会发现写链表代码**最考验逻辑思维能力**。链表代码到处都是指针操作，边界值条件的处理，稍有不慎就bug。练习写链表能考察我们的细心，以及考虑问题是否全面，思维缜密性。  
ps：如果链表练习的差不多了，可以尝试实现下LRU，毕竟人生不设限，处处都是挑战。  
附文一篇希望大家早日实现[LRU缓存算法][LRU]

[20201128213005440.png]: /images/20221120/3fffd0b8fe764d60a3f6dda771402a7b.png
[20201128213722198.png]: /images/20221120/63d1b083405f433f82d94ce7e3e615aa.png
[20201128213925820.png]: https://img-blog.csdnimg.cn/20201128213925820.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020112822074872.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/jiadajing267/article/details/109740745
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201128225439851.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201128233217882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWRhamluZzI2Nw==,size_16,color_FFFFFF,t_70
[Link 2]: https://leetcode-cn.com/problems/linked-list-cycle/solution/yi-wen-gao-ding-chang-jian-de-lian-biao-wen-ti-h-2/
[2 _]: https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/
[LRU]: https://www.jianshu.com/p/b1ab4a170c3c