如果当前还未定位到指定的节点,只是拿到链表的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;
- }
- }
以上,就是对「 数组与链表 」的一些思考。
(编辑:ASP站长网)
|