學好C語言必要深入學習的數組與鏈表演算法
1 人贊了文章
什麼是數組？
數組簡單來說就是將所有的數據排成一排存放在系統分配的一個內存塊上，通過使用特定元素的索引作為數組的下標，可以在常數時間內訪問數組元素的這麼一個結構；
為什麼能在常數時間內訪問數組元素？
為了訪問一個數組元素，該元素的內存地址需要計算其距離數組基地址的偏移量。需要用一個乘法計算偏移量，再加上基地址，就可以獲得某個元素的內存地址。首先計算元素數據類型的存儲大小，然後將它乘以元素在數組中的索引，最後加上基地址，就可以計算出該索引位置元素的地址了；整個過程可以看到需要一次乘法和一次加法就完成了，而這兩個運算的執行時間都是常數時間，所以可以認為數組訪問操作能在常數時間內完成；
數組的優點
- 簡單且易用；
- 訪問元素快（常數時間）；
數組的缺點
- 大小固定：數組的大小是靜態的（在使用前必須制定數組的大小）；
- 分配一個連續空間塊：數組初始分配空間時，有時候無法分配能存儲整個數組的內存空間（當數組規模太大時）；
- 基於位置的插入操作實現複雜：如果要在數組中的給定位置插入元素，那麼可能就會需要移動存儲在數組中的其他元素，這樣才能騰出指定的位置來放插入的新元素；而如果在數組的開始位置插入元素，那麼這樣的移動操作開銷就會很大。
關於數組的一些問題思考
1）在索引沒有語義的情況下如何表示沒有的元素？
我們創建的數組的索引可以有語義也可以沒有語義，比如我現在只是單純的想存放100，98，96這三個數字，那麼它們保存在索引為0，1，2的這幾個地方或者其他地方都可以，無論它們之間的順序怎樣我都不關心，因為它們的索引是沒有語義的我只是想把它們存起來而已；但是如果它們變成了學號為1，2，3這幾個同學對應的成績，那麼它們的索引就有了語義，索引0對應了學號為1的同學的成績，索引1對應了學號2的同學，索引2對應了學號3的同學，因為數組的最大的優點是訪問元素是在常數時間，所以我們使用數組最好就是在索引有語義的情況下；
好了，那麼如果在索引沒有語義的情況下，我們如何表示沒有的元素呢？例如上圖中，對於用戶而言，訪問索引為3和4的數組元素是違法的，因為它們根本就不存在，我們如何表示沒有的元素呢？
表示為0或者-1？
2）如何添加元素和刪除元素呢？
我們知道，數組的明顯缺點是在創建之前需要提前聲明好要使用的空間，那麼當我們空間滿了該如何處理呢？又該如何刪除元素呢？在Java中提供給我們的默認數組是不支持這些功能的，我們需要開發屬於自己的數組類才行；
使用泛型封裝自己的數組類
我們需要自己創建一個Array類，並實現一些增刪改查的功能，大體的結構如下：
public class Array<E>{
private E[] data;
private int size;
/* 一些成員方法 */
}
我們需要一個成員變數來保存我們的數據，這裡是data，然後需要一個int類型來存放我們的有效元素的個數，在這裡我們沒有必要再多定義一個表示數組空間的變數，因為這裡的空間大小就是data.length；
默認的構造函數
我們需要創建一些方法來初始化我們的數組，那肯定是需要傳一個capacity來表示數組的容量嘛：
// 構造函數，傳入數組的容量capacity構造Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
當然我們也需要創建一個默認的構造函數來為不知道初始該定義多少的用戶一個默認大小的數組：
// 無參數的構造函數，默認數組的容量capacity=10
public Array() {
this(10);
}
這裡演示的話給個10差不多了，實際可能會更複雜一些…
成員方法
就是增刪改查嘛，不過這裡需要注意的是，為了實現我們自己的動態數組，在增加和刪除中，我們對臨界值進行了判斷，動態的增加或者縮小數組的大小，而且提供了一些常用友好的方法給用戶；
// 獲取數組的容量
public int getCapacity() {
return data.length;
}
// 獲取數組中的元素個數
public int getSize() {
return size;
}
// 返回數組是否為空
public boolean isEmpty() {
return size == 0;
}
// 在index索引的位置插入一個新元素e
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if (size == data.length)
resize(2 * data.length);
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
// 向所有元素後添加一個新元素
public void addLast(E e) {
add(size, e);
}
// 在所有元素前添加一個新元素
public void addFirst(E e) {
add(0, e);
}
// 獲取index索引位置的元素
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素為e
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
// 查找數組中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e))
return true;
}
return false;
}
// 查找數組中元素e所在的索引，如果不存在元素e，則返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e))
return i;
}
return -1;
}
// 從數組中刪除index位置的元素, 返回刪除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++)
data[i - 1] = data[i];
size--;
data[size] = null; // loitering objects != memory leak
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 從數組中刪除第一個元素, 返回刪除的元素
public E removeFirst() {
return remove(0);
}
// 從數組中刪除最後一個元素, 返回刪除的元素
public E removeLast() {
return remove(size - 1);
}
// 從數組中刪除元素e
public void removeElement(E e) {
int index = find(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d
", size, data.length));
res.append([);
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1)
res.append(", ");
}
res.append(]);
return res.toString();
}
// 將數組空間的容量變成newCapacity大小
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++)
newData[i] = data[i];
data = newData;
}
- 注意：為了更好的展示代碼而不太浪費空間，所以這裡使用//的風格來注釋代碼；
- 特別注意：在remove方法中，縮小數組的判斷條件為size == data.length / 4 && data.length / 2 != 0，這是為了防止複雜度抖動和安全性；
簡單時間複雜度分析
添加操作
在添加操作中，我們可以明顯看到，addLast()方法是與n無關的，所以為O(1)複雜度；而addFirst()和add()方法都涉及到挪動數組元素，所以都是O(n)複雜度，包括resize()方法；綜合起來添加操作的複雜度就是O(n)；
刪除操作
在刪除操作中，與添加操作同理，綜合來看刪除操作的複雜度就是O(n)；
修改操作
在修改操作中，如果我們知道了需要修改元素的索引，那麼我們就可以在常數時間內找到元素並進行修改操作，所以很容易的知道這個操作時一個複雜度為O(1)的操作，所以修改操作的複雜度就是O(1)；但另外一種情況是我們不知道元素的索引，那麼我們就需要先去查詢這個元素，我把這歸結到查詢操作中去；
查詢操作
在查詢操作中，如果我們已知索引，那麼複雜度為O(1)；如果未知索引，我們需要遍歷整個數組，那麼複雜度為O(n)級別；
總結
以上我們簡單分析了我們自己創建的數組類的複雜度：
- 增加：O(n)；
- 刪除：O(n)；
- 修改：已知索引 O(1)；未知索引 O(n)；
- 查詢：已知索引 O(1)；未知索引 O(n)；
均攤複雜度
如果細心的同學應該可以注意到，在增加和刪除的複雜度分析中，如果我們都只是對最後一個元素進行相應的操作的話，那麼對應的O(n)的複雜度顯然是不合理的，我們之所以將他們的複雜度定義為O(n)，就是因為在我們通常的複雜度分析中我們需要考慮最壞的情況，也就是對應的需要使用resize()方法擴容的情況，但是這樣的情況並不是每一次都出現，所以我們需要更加合理的來分析我們的複雜度，這裡提出的概念就是：均攤複雜度；
假設我們現在的capacity為5，並且每一次的添加操作都使用addLast()方法，那麼我們在使用了五次addLast()方法之後就會觸發一次resize()方法，在前五次的addLast()方法中我們總共進行了五次基本操作，也就是給數組的末尾添加上一個元素，在進行第六次addLast()方法的時候，觸發resize()方法，就需要進行一次元素的轉移，共5次操作（轉移五個元素嘛），然後再在末尾加上一個元素，也就是總共進行了11次操作；
也就是說：6次addLast()操作，觸發resize()方法，總共進行了11次操作，平均下來，每次addLast()操作，進行了2次基本操作（約等於）；那麼依照上面的假設我們可以進一步推廣為：假設capacity為n，n+1次addLast()操作，觸發resize()方法，總共進行了2n+1次基本操作，平均來講，每次addLast()操作，進行了2次基本操作，這樣也就意味著，均攤下來的addLast()方法的複雜度為O(1)，而不是之前分析的O(n)，這樣的均攤複雜度顯然比最壞複雜度來得更有意義，因為不是每一次的操作都是最壞的情況！
同理，我們看removeLast()對應的均攤複雜度也為O(1)；
複雜度震蕩
在我們的remove方法中，我們判斷縮小容量的條件為size == data.length / 4 && data.length / 2 != 0，這樣是為了防止複雜度震蕩和安全性（因為縮小到一定的時候容量可能為1），這又是怎麼一回事呢？我們考慮一下將條件改為size == data.length / 2的時候，出現的如下圖這樣的情況：
當我們數組已經滿元素的情況下，使用一次addLast方法，因為觸發resize，數組容量擴容為當前的兩倍，所以此時複雜度為O(n)；這時候我們立即使用removeLast，因為此時的容量等於n/2，所以會馬上產生縮小容量的操作，此時複雜度為O(n)；我們之前明明通過均攤複雜度分析出我們的兩個操作都為O(1)，而此時卻產生了震蕩，為了避免這樣的操作，我們需要懶操作一下，也就是在remove的時候不要立即縮容，而是等到size == capacity / 4的時候再縮小一半，這樣就有效的解決了複雜度震蕩的問題；
Java中的ArrayList的擴容
上面我們已經實現了自己的數組類，我們也順便看看Java中的ArrayList是怎麼寫的，其他的方法可以自己去看看，這裡提出來一個grow()的方法，來看看ArrayList是怎麼實現動態擴容的：
從上面的源碼我們可以看到ArrayList默認增容是增加當前容量的0.5倍（>> 1即乘以0.5）
鏈表
什麼是鏈表
鏈表是一種用於存儲數據集合的數據結構，它是最簡單的動態數據結構，我們在上面雖然實現了動態數組，但這僅僅是對於用戶而言，其實底層還是維護的一個靜態的數組，它之所以是動態的是因為我們在add和remove的時候進行了相應判斷動態擴容或縮容而已，而鏈表則是真正意義上動態的數據結構；
鏈表的優點
- 真正的動態，不需要處理固定容量的問題；
- 能夠在常數時間內擴展容量；
對比我們的數組，當創建數組時，我們必須分配能存儲一定數量元素的內存，如果向數組中添加更多的元素，那麼必須創建一個新的數組，然後把原數組中的元素複製到新數組中去，這將花費大量的時間；當然也可以通過給數組預先設定一個足夠大的空間來防止上述時間的發生，但是這個方法可能會因為分配超過用戶需要的空間而造成很大的內存浪費；而對於鏈表，初始時僅需要分配一個元素的存儲空間，並且添加新的元素也很容易，不需要做任何內存複製和重新分配的操作；
鏈表的缺點
- 喪失了隨機訪問的能力；
- 鏈表中的額外指針引用需要浪費內存；
鏈表有許多不足。鏈表的主要缺點在於訪問單個元素的時間開銷問題；數組是隨時存取的，即存取數組中任一元素的時間開銷為O(1)，而鏈表在最差情況下訪問一個元素的開銷為O(n)；數組在存取時間方面的另一個優點是內存的空間局部性，由於數組定義為連續的內存塊，所以任何數組元素與其鄰居是物理相鄰的，這極大得益於現代CPU的緩存模式；
鏈表和數組的簡單對比
- 數組最好用於索引有語意的情況，最大的優點：支持快速查詢；
- 鏈表不適用於索引有語意的情況，最大的優點：動態；
實現自己的鏈表類
public class LinkedList<E> {
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
@Override
public String toString() {
return e.toString();
}
}
private Node dummyHead;
private int size;
public LinkedList() {
dummyHead = new Node();
size = 0;
}
// 獲取鏈表中的元素個數
public int getSize() {
return size;
}
// 返回鏈表是否為空
public boolean isEmpty() {
return size == 0;
}
// 在鏈表的index(0-based)位置添加新的元素e
// 在鏈表中不是一個常用的操作，練慣用：）
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Illegal index.");
Node prev = dummyHead;
for (int i = 0; i < index; i++)
prev = prev.next;
prev.next = new Node(e, prev.next);
size++;
}
// 在鏈表頭添加新的元素e
public void addFirst(E e) {
add(0, e);
}
// 在鏈表末尾添加新的元素e
public void addLast(E e) {
add(size, e);
}
// 獲得鏈表的第index(0-based)個位置的元素
// 在鏈表中不是一個常用的操作，練慣用：）
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Illegal index.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++)
cur = cur.next;
return cur.e;
}
// 獲得鏈表的第一個元素
public E getFirst() {
return get(0);
}
// 獲得鏈表的最後一個元素
public E getLast() {
return get(size - 1);
}
// 修改鏈表的第index(0-based)個位置的元素為e
// 在鏈表中不是一個常用的操作，練慣用：）
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Update failed. Illegal index.");
Node cur = dummyHead.next;
for (int i = 0; i < index; i++)
cur = cur.next;
cur.e = e;
}
// 查找鏈表中是否有元素e
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e))
return true;
cur = cur.next;
}
return false;
}
// 從鏈表中刪除index(0-based)位置的元素, 返回刪除的元素
// 在鏈表中不是一個常用的操作，練慣用：）
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
// E ret = findNode(index).e; // 兩次遍歷
Node prev = dummyHead;
for (int i = 0; i < index; i++)
prev = prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
// 從鏈表中刪除第一個元素, 返回刪除的元素
public E removeFirst() {
return remove(0);
}
// 從鏈表中刪除最後一個元素, 返回刪除的元素
public E removeLast() {
return remove(size - 1);
}
// 從鏈表中刪除元素e
public void removeElement(E e) {
Node prev = dummyHead;
while (prev.next != null) {
if (prev.next.e.equals(e))
break;
prev = prev.next;
}
if (prev.next != null) {
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
鏈表虛擬頭結點的作用
- 為了屏蔽掉鏈表頭結點的特殊性；
- 因為頭結點是沒有前序結點的，所以我們不管是刪除還是增加操作都要對頭結點進行單獨的判斷，為了我們編寫邏輯的方便，引入了一個虛擬頭結點的概念；
簡單複雜度分析
我們從鏈表的操作中可以很容易的看出，對於增刪改查這幾個操作的複雜度都是O(n)的，但是如果我們只是對鏈表頭進行增/刪/查的操作的話，那麼它的複雜度就是O(1)的，這裡也可以看出來我們的鏈表適合乾的事情了..
LeetCode相關題目參考
1.兩數之和
參考答案：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int [] res = new int[2];
if(numbers==null||numbers.length<2)
return res;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length; i++){
if(!map.containsKey(target-numbers[i])){
map.put(numbers[i],i);
}else{
res[0]= map.get(target-numbers[i]);
res[1]= i;
break;
}
}
return res;
}
}
2.兩數相加
參考答案：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode p = l1, q = l2, curr = dummyHead;
int carry = 0;
while (p != null || q != null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr.next = new ListNode(sum % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
return dummyHead.next;
}
19.刪除鏈表的倒數第N個節點（劍指Offer面試題22）
我的答案：（13ms）
public ListNode removeNthFromEnd(ListNode head, int n) {
// 正確性判斷
if (null == head || null == head.next) {
return null;
}
int num = 0;
// 定義一個虛擬頭結點方便遍歷鏈表
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
// 一次遍歷找到鏈表的總數
while (null != prev.next) {
num++;
prev = prev.next;
}
// 二次遍歷刪除對應的節點
prev = dummyHead;
for (int i = 0; i < num - n; i++) {
prev = prev.next;
}// end for:找到了刪除節點的前序節點
ListNode delNode = prev.next;
prev.next = prev.next.next;
delNode.next = null;
// 返回頭結點
return dummyHead.next;
}
我的答案2：（16ms）
public ListNode removeNthFromEnd(ListNode head, int n) {
// 正確性判斷
if (null == head || null == head.next) {
return null;
}
HashMap<Integer, ListNode> map = new HashMap<>();
// 定義一個虛擬頭結點方便遍歷鏈表
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
map.put(0, dummyHead);
// 一次遍歷，將序號與ListNode對應存入map中
for (int i = 1; null != prev.next; i++, prev = prev.next) {
map.put(i, prev.next);
}
// 刪除對應的節點
int delNodeNum = map.size() - n;
ListNode delNode = map.get(delNodeNum);
prev = map.get(delNodeNum - 1);
prev.next = prev.next.next;
delNode.next = null;// help GC
// 返回頭結點
return dummyHead.next;
}
參考答案：（26ms）
public ListNode removeNthFromEnd(ListNode head, int n) {
// 正確性判斷
if (null == head || null == head.next) {
return null;
}
// 定義虛擬頭結點方便遍歷
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
// 定義快慢兩個節點
ListNode fast = dummyHead;
ListNode slow = dummyHead;
// 讓fast先跑到第n個位置
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
// 再讓兩個一起移動，當fast為尾節點時slow的位置即刪除元素的位置
while (null != fast) {
fast = fast.next;
slow = slow.next;
}
ListNode delNode = slow.next;
slow.next = slow.next.next;
delNode.next = null;// help GC.
return dummyHead.next;
}
21.合併兩個有序鏈表（劍指Offer面試題25）
我的答案：（13ms）
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 正確性判斷
if (null == l1) {
return l2;
}
if (null == l2) {
return l1;
}
// 定義一個虛擬頭結點方便遍歷
ListNode dummyHead = new ListNode(-1);
dummyHead.next = l1;
ListNode pre = dummyHead;
// 遍歷l1鏈表
int len1 = 0;
while (null != pre.next) {
len1++;
pre = pre.next;
}
int[] nums1 = new int[len1];
// 保存l1鏈表的數據
pre = dummyHead;
for (int i = 0; i < len1; i++) {
nums1[i] = pre.next.val;
pre = pre.next;
}
// 遍歷l2鏈表
int len2 = 0;
dummyHead.next = l2;
pre = dummyHead;
while (null != pre.next) {
len2++;
pre = pre.next;
}
int[] nums2 = new int[len2];
// 保存l2鏈表的數據
pre = dummyHead;
for (int i = 0; i < len2; i++) {
nums2[i] = pre.next.val;
pre = pre.next;
}
int[] nums = new int[len1 + len2];
// 將兩個鏈表的數據整合併排序
System.arraycopy(nums1, 0, nums, 0, len1);
System.arraycopy(nums2, 0, nums, len1, len2);
Arrays.sort(nums);
// 拼接一個鏈表
ListNode dummy = new ListNode(-1);
pre = dummy;
for (int i = 0; i < nums.length; i++) {
ListNode node = new ListNode(nums[i]);
pre.next = node;
pre = pre.next;
}
return dummy.next;
}
參考答案：（15ms）
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode head = null;
if (l1.val < l2.val) {
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
return head;
}
74.搜索二維矩陣（劍指Offer面試題4）
參考答案：（8ms）
public boolean searchMatrix(int[][] matrix, int target) {
// 正確性判斷
if (null == matrix || 0 == matrix.length) {
return false;
}
if (null == matrix[0] || 0 == matrix[0].length) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int start = 0, end = row * col - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int number = matrix[mid / col][mid % col];
if (number == target) {
return true;
} else if (number > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
141.環形鏈表
我的答案：（14ms）
public boolean hasCycle(ListNode head) {
// 正確條件判斷
if (null == head || null == head.next) {
return false;
}
// 引入虛擬頭結點
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
HashMap<ListNode, Integer> map = new HashMap<>();
ListNode prev = dummyHead;
// 遍歷鏈表
while (null != prev.next) {
if (map.containsKey(prev.next)) {
return true;
} else {
map.put(prev.next, prev.next.val);
prev = prev.next;
}
}
// 如果遍歷到了鏈表尾巴都沒找到則返回false
return false;
}
參考答案：（3ms）
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
// move 2 steps
fast = fast.next.next;
// move 1 step
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
147.對鏈表進行插入排序
參考答案：（38ms）
public ListNode insertionSortList(ListNode head) {
// 正確性判斷
if (null == head || null == head.next) {
return head;
}
// 定義一個新的節點，這個節點的作用是一個一個把head開頭的鏈表插入到dummy開頭的鏈表裡
ListNode dummy = new ListNode(-1);
// 類似於冒泡排序法的遍歷整個鏈表
while (null != head) {
ListNode pre = dummy;
while (null != pre.next && pre.next.val < head.val) {
pre = pre.next;
}
ListNode temp = head.next;
head.next = pre.next;
pre.next = head;
head = temp;
}
return dummy.next;
}
148.排序鏈表
我的答案：（829ms）
public ListNode sortList(ListNode head) {
// 正確性判斷
if (null == head || null == head.next) {
return head;
}
// 引入虛擬頭結點方便遍歷
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
List<Integer> vals = new ArrayList<>();
ListNode prev = dummyHead;
// 遍歷一遍數組，將數據存入排好序存入vals集合中
while (null != prev.next) {
// 每一次都將val值插入到正確的地方
int index = 0;
for (int i = 0; i < vals.size(); i++) {
if (prev.next.val >= vals.get(i)) {
index = i + 1;
}
}
vals.add(index, prev.next.val);
prev = prev.next;
}
// 連接鏈表
prev = dummyHead;
for (int i = 0; i < vals.size(); i++) {
ListNode node = new ListNode(vals.get(i));
prev.next = node;
prev = prev.next;
}
return dummyHead.next;
}
參考答案：（4ms）
public ListNode sortList(ListNode head) {
// 正確性判斷
if (null == head || null == head.next) {
return head;
}
// 第一次遍歷：找到鏈表長度
int len = 0;
ListNode cur = head;
while (null != cur) {
len++;
cur = cur.next;
}
// 第二次遍歷：保存鏈表的值
int[] nums = new int[len];
cur = head;
for (int i = 0; i < len; i++) {
nums[i] = cur.val;
cur = cur.next;
}
// 第三次遍歷：改變鏈表的值
Arrays.sort(nums);
cur = head;
for (int i = 0; i < len; i++) {
cur.val = nums[i];
cur = cur.next;
}
return head;
}
這裡想吐槽一下：因為上面的演算法遍歷了三次鏈表，我想著使用ArrayList來少一次遍歷結果發現運算速度達到了20ms左右..時間好像都花在了ArrayList轉數組這個操作上了…這或許就是傳說中的負優化吧…
203.刪除鏈表中的節點（劍指Offer面試題18）
參考答案：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 定義一個虛擬頭結點
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode prev = dummyHead;
while (prev.next != null) {
if (prev.next.val == val) {
prev.next = prev.next.next;
} else {
prev = prev.next;
}
}
return dummyHead.next;
}
}
206.反轉鏈表（劍指Offer面試題6、面試題24）
我的答案：（7ms）
public ListNode reverseList(ListNode head) {
// 正確性判斷
if (null == head || null == head.next) {
return head;
}
// 定義一個虛擬頭結點
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
HashMap<Integer, ListNode> map = new HashMap<>();
ListNode prev = dummyHead;
// 存儲節點順序信息
for (int i = 0; null != prev.next; i++) {
map.put(i, prev.next);
prev = prev.next;
}
int listSize = map.size();
// 反轉鏈表
for (int i = listSize - 1; i > 0; i--) {
map.get(i).next = map.get(i - 1);
}
map.get(0).next = null;
// 返回頭結點
return map.get(listSize - 1);
}
參考答案：（0ms）
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while (null != head) {
ListNode temp = head;
head = head.next;
temp.next = pre;
pre = temp;
}
return pre;
}
442.數組中重複的數據（劍指Offer面試題3）
我的答案：（56ms）
public List<Integer> findDuplicates(int[] nums) {
List<Integer> result = new ArrayList<>();
// 正確性判斷
if (null == nums || 0 == nums.length) {
return result;
}
// 創建一個HashMap，K值存位置，V值存數據
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 如果存在重複的V值那麼則有重複的元素存在
if (map.containsKey(nums[i])) {
result.add(nums[i]);
}
map.put(nums[i], i);
}
return result;
}
參考答案：（14ms）
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
for (int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) nums[index] *= -1;
else {
res.add(index + 1);
}
}
return res;
}
上面這個方法我DEBUG了一會兒終於搞懂了，如果有兩個重複的數字，那麼nums[index]位置的數字一定是一個複數，但是如果這個index值超過了nums.length，就會報錯啊..這個只能算一個巧解吧…
推薦閱讀：