数据结构系列1数组和链表

数组

数组是一种线性表数据结构,它是一组连续的内存空间。它存储一组具有相同类型的数据。

查询: 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;
}