数据结构与算法-循环链表与双向链表【四】

悠悠 2023-06-24 08:13 1阅读 0赞

我们下面讨论的前提是：

1，链表有一个辅助头节点，这个辅助头结点的next才是真正的数据节点。

2，单链表的定义：

// Definition for singly-linked list.
      
      function ListNode(val) { 
          this.val = val;
          this.next = null;
      }

### 循环链表 ###

单链表只有一个头结点 和一个尾节点。

循环链表：作为特殊的单链表的一种，尾节点的指针域，指向头结点，是一个闭环。 【尾部指向头部】

### 循环链表遍历 ###

单链表遍历完成的条件是 node == null

单循环连标遍历完成的条件是 node == head，head为头指针。

// 单链表遍历
        function iteratorList(node) { 
            while(node != null) { 
                console.log(node.val)
                node = node.next
            }
            
        }
        
        // 循环链表遍历
        function iteratorList(node) { 
            let head = node
            while(node.next != head) { 
                console.log(node.val)
                node = node.next
            }
        }

### 头指针 和 尾指针来表示单循环链表 ###

也就是说，给予我们的指针是指向头节点 和 尾节点。

头指针表示的单循环链表，寻找第一个数据节点:R.next 时间复杂度为O(1)，寻找最后一个数据节点，时间复杂度为O(n)。

尾指针表示的单循环链表，寻找第一个数据节点:R.next.next，寻找最后一个数据节点，为R本身。时间复杂度都是O(1).

### 合并两个单循环链表 ###

给我们的节点是尾指针节点。NodeA NodeB都是指向两个单循环链表的尾节点。

function mergeTwoLoopSingleList(Na, Nb) { 
            let p = Na.next // 保存头节点
            Na.next = Nb.next.next
            Nb.next = p
            return p
        }

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

### 双向链表 ###

双向链表 除了有一个数据域，有两个指针域，一个存前一个节点的地址，一个存后一个节点的地址。

因为节点本身存储了前驱和后继节点的地址，所以删除某个位置的元素以及 在某个位置插入元素我们不一定非要找到前一个节点进行操作。

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

### 链表 和 顺序表的比较 ###

链表是动态可变的  
  顺序表需要预先分配空间，会存在数据溢出或者空间闲置，存储空间不灵活。

链表插入和删除元素只需要移动指针即可。在确定位置的情况，时间复杂度为O(1)  
 顺序表插入删除元素会移动的元素,时间复杂度为O(n)

链表存取元素最坏的情况需要遍历整个链表，时间复杂度为O(n)  
  顺序表查找元素由于存储地址连续知道头元素，就能知道特定位置的元素的地址，时间复杂度为O(1)

顺序表是存取快，适合预先知道数据，不经常改变，但是经常存取的数据集合。  
  链表是插入删除快，适合经常动态变化的数据集合，

### 有序线性表的合并 ###

> **顺序表的实现**

用顺序表的实现，就可以理解为用数组来，也就是两个有序数组的合并，合并之后也需要是一个有序的。

看这里—> [https://blog.csdn.net/a5534789/article/details/102669074][https_blog.csdn.net_a5534789_article_details_102669074]

> **链表的实现**

原理是类似的，但是比较好的方法是直接将某一个链表的head头指针作为新排序表的头节点，这样空间复杂度为O(1)

function mergeTwoOrderList(l1, l2) { 
            let n1 = l1.next, n2 = l2.next
            let newL = l1
            while(n1 && n2) { 
                if (n1.val <= n2.val) { 
                    newL.next = n1
                    n1 = n1.next
                } else { 
                    newL.next = n2
                    n2 = n2.next
                }
                newL = newL.next
            }
            // while(n1) { newL.next = n1 } 错误
            
            // 优化
            // if (n1) newL.next = n1
            // if (n2) newL.next = n1
            newL.next = n1 || n2
            return newL
        }

### 两个多项式的求和 ###

现在有多项式  
  `p1 = 8 + 2 * X^3 + 9 * X^6 + 3 * X^8`  
以及多项式  
  `p2 = 1 + 5 * X^3 - 9* X^6`

怎么求和呢？

是的，通过顺序表(数组方式)和链表都可以来做。先提取出系数与指数，然后就回归到了合并两个有序表的问题上来了 。

[https_blog.csdn.net_a5534789_article_details_102669074]: https://blog.csdn.net/a5534789/article/details/102669074