數(shù)組

數(shù)組:內(nèi)存里連續(xù)的一段存儲區(qū)域

取:取元素時間復雜度為O(1)

插入:需要挪動插入位置后面的元素,時間復雜度為O(n)

刪除:同插入,后面的元素需要向前挪動,時間復雜度為O(n)

鏈表

單向鏈表:用一個指針鏈向下一個元素

雙向鏈表:用倆個指針鏈向上一個元素和下一個元素

增加刪除只需要更改指針指向即可,時間復雜度O(1)

查找時間復雜度是O(n)

練習

1. leetcode206反轉(zhuǎn)鏈表

   輸入: 1->2->3->4->5->NULL
   輸出: 5->4->3->2->1->NULL
   

   思路:定義倆個變量,記錄當前節(jié)點和上一個節(jié)點,采用倆數(shù)交換的方式進行反轉(zhuǎn)

   class Solution {
       public ListNode reverseList(ListNode head) {
           ListNode cur = head;
           ListNode prev = null;
           ListNode tempNext = null;
           while (cur != null) {
               tempNext = cur.next;
               cur.next = prev;
               prev = cur;
               cur = tempNext;
           }
           return prev;
       }
   }
   

2. leetcode24兩兩交互鏈表中的節(jié)點

   給定 1->2->3->4, 你應該返回 2->1->4->3.
   

   遞歸解乏

       public static ListNode swapPairs(ListNode head) {
           if (head == null || head.next == null) {
               return head;
           }
           ListNode next = head.next;
           head.next = swapPairs(next.next);
           next.next = head;
           return next;
       }
   

   非遞歸解法

       public static ListNode swapPairs2(ListNode head) {
           ListNode prev = new ListNode(0);
           prev.next = head;
           ListNode temp = prev;
           while (temp.next != null && temp.next.next != null) {
               ListNode start = temp.next;
               ListNode end = temp.next.next;
               temp.next = end;
               start.next = end.next;
               end.next = start;
               temp = start;
           }
           return prev.next;
       }
   

3. 環(huán)形鏈表

   給定一個鏈表宣鄙，判斷鏈表中是否有環(huán)糕档。

   輸入：head = [3,2,0,-4], pos = 1
   輸出：true
   解釋：鏈表中有一個環(huán)霞溪，其尾部連接到第二個節(jié)點尤误。
   

   img

思路:如何判斷一個鏈表是否有環(huán)

1. 硬做(在0.5s內(nèi)判斷會不會走到null,性能很差)

2. 把走過的節(jié)點放到set中,每到新節(jié)點判斷set中有沒有進行判重,時間復雜度O(n)

       public boolean hasCycle(ListNode head) {
           Set<ListNode> nodes = new HashSet<>();
           while (head != null) {
               if (nodes.contains(head)) {
                   return true;
               }
               nodes.add(head);
               head = head.next;
           }
           return false;
       }
   

3. 龜兔賽跑式(快慢指針),快指針每次走倆步,慢指針每次走一步,快慢相遇說明有環(huán)

       public boolean hasCycle(ListNode head) {
           if (head == null || head.next == null) {
               return false;
           }
           ListNode fast = head;
           ListNode slow = head;
           while (fast.next != null && fast.next.next != null) {
               slow = slow.next;
               fast = fast.next.next;
               if (slow == fast) {
                   return true;
               }
           }
           return false;
       }