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

如果当前还未定位到指定的节点，只是拿到链表的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; 
    } 
} 

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

（编辑：PHP编程网 - 黄冈站长网）

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