算法一看就懂之「 数组与链表 」

假如当前还未定位到指定的节点，只是拿到链表的Head，这个时辰要去删除此链表中某个牢靠内容的节点，则必要先查找到谁人节点，这个查找的举措又是一个遍历举措了，这个遍历查找的时刻伟大度却是O(n)，两者加起来总的时刻伟大度着实是O(n)的。

着实就算是已经定位到了某个要删除的节点了，删除逻辑也不简朴。以“删除上图的E节点”为例，若是当前链表指针已经定位到了E节点，删除的时辰，必要将这个E节点的前面一个节点H的后继指针改为指向A节点，那么E节点就会自动脱落了，可是当前链表指针是定位在E节点上，怎样去改变H节点的后续指针呢，对付“单向链表”而言，这个时辰必要从新遍历一遍整个链表，找到H节点去修改厥后继指针的内容，以是时刻伟大度是O(n)，但假如当前是“双向链表”，则不必要遍历，直接通过前继指针即可找到H节点，时刻伟大度是O(1)，这里就是“双向链表”相等于“单向链表”的上风地址。

三、「 数组和链表 」的算法拭魅战?

通过上面的先容我们可以看到「 数组 」和「 链表 」各有上风，而且时刻伟大度在差异的操纵环境下也不沟通，不能简朴一句O(1)或O(n)。以是下面我们找了个常用的算法题来操练操练。

算法题：反转一个单链表 
输入: 1->2->3->4->5->NULL 
输出: 5->4->3->2->1->NULL 
 
/** 
 * Definition for singly-linked list. 
 * public class ListNode { 
 *     int val; 
 *     ListNode next; 
 *     ListNode(int x) { val = x; } 
 * } 
 */ 
class Solution { 
    public ListNode reverseList(ListNode head) { 
        //界说一个前置节点变量，默认是null，由于对付第一个节点而言没有前置节点 
        ListNode pre = null; 
        //界说一个当前节点变量，起首将头节点赋值给它 
        ListNode curr = head; 
        //遍历整个链表，直到当前指向的节点为空，也就是最后一个节点了 
        while(curr != null){ 
            //在轮回体里会去改变当前节点的指针偏向，原来当前节点的指针是指向的下一个节点，此刻必要改为指向前一个节点，可是假如直接就这么修改了，那链条就断了，再也找不到后头的节点了，以是起首必要将下一个节点先姑且生涯起来，赋值到temp中，以备后续行使 
            ListNode temp = curr.next; 
            //开始处理赏罚当前节点，将当前节点的指针指向前面一个节点 
            curr.next = pre; 
            //将当前节点赋值给变量pre，也就是让pre移动一步，pre指向了当前节点 
            pre = curr; 
            //将之前世存的姑且节点（后头一个节点）赋值给当前节点变量 
            curr = temp; 
            //轮回体执行链表状态改观环境： 
            //NULL<-1  2->3->4->5->NULL 
            //NULL<-1<-2  3->4->5->NULL 
            //NULL<-1<-2<-3  4->5->NULL 
            //NULL<-1<-2<-3<-4  5->NULL 
            //NULL<-1<-2<-3<-4<-5 
            //轮回体遍历完之后，pre指向5的节点 
        } 
        //完成，时刻伟大度为O(n) 
        return pre; 
    } 
} 

以上，就是对「 数组与链表 」的一些思索。

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!