数组
数组是一种线性表数据结构,它是一组连续的内存空间。它存储一组具有相同类型的数据。
查询: O(1)
插入: O(n)
删除: O(n)
思考题: 数组是如何实现元素的快速访问的呢?
计算会为记录每个数据类型的大小,由于数据的内存空间是连续的,所以知道了首地址,知道的元素的下标,就可以计算出来:
findItemAddr = firstItemAddr + sizeOf(dataType) * index
思考题: 数组的下标为什么从0开始的呢?
从数据存储的内存模型上看,下标其实是"偏移". 正是因为下标是从0开始的,所以我们才能使用上面的计算公式来确定元素的问题。如果从1开始的时候,上面的公式就变成了 findItemAddr = firstItemAddr + sizeOf(dataType) * (index-1)
这样对CPU来说,是多一次减法指令.
链表
非定长的,地址不连续的. 链表通过指针将一组零散的内存块串联在一起。
查找: O(n)
插入,删除 O(1)
LeetCode题目
206反转链表
题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
代码实现
迭代
public ListNode reverseList(ListNode head) {
ListNode cur = null;
ListNode pre = null;
while (head != null) {
(cur = new ListNode(head.val)).next = pre;
pre = cur;
head = head.next;
}
return cur;
}
时间复杂度O(n)
, 空间复杂度O(n)
public ListNode reverseList(ListNode head) {
ListNode cur = null;
ListNode reverse = reverse(head, cur);
return reverse;
}
private ListNode reverse(ListNode head,
ListNode pre) {
ListNode newHead = null;
if (head != null) {
newHead = reverse(head.next, head);
head.next = pre;
} else {
newHead = pre;
}
return newHead;
}
时间复杂度O(n)
, 空间复杂度O(n)
最优解
迭代
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
时间复杂度O(n)
, 空间复杂度O(n)
递归
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
时间复杂度O(n)
, 空间复杂度O(n)
24两两交换链表中的节点
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
给定 1->2->3->4, 你应该返回 2->1->4->3.
代码实现
public ListNode swapPairs(ListNode head) {
ListNode newHead = head;
ListNode pre = null;
while (null != head && null != head.next) {
ListNode n2 = head.next;
head.next = head.next.next;
if(null == pre){
newHead = n2;
}else{
pre.next = n2;
}
n2.next = head;
pre = head;
head = head.next;
}
return newHead;
}