Leetcode題目總結-Linkedlist-題目206和234

  今天做了兩道非常有意思的題目，leetcode上的206和234。這兩道題目都是和連結清單有關的，并且都會運用的reverse list這個思想。

  pro(206): Reverse a singly linked list.

 My solution1: 

如果是數組實作回非常簡單，但是linkedlist如何實作？

第一個想法是，建立一個數組，周遊linkedlist中的所有元素，并記錄在數組中。再周遊一次，此時修改在linked list中的每一個元素的值. 這個方法需要三次周遊.

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        
        //第一次周遊，是用來計算連結清單中有多少個元素，即n
        ListNode Num = head;
        int n = 1;
        while(Num.next != null){ //判斷連結清單是否到頭
            Num = Num.next;
            n++;
        }
        
        //第二次周遊，是用來在數組中紀錄連結清單中的元素
        ListNode Record = head;
        int[] Val = new int[n];
        for(int i = 0; i < n; i++){
            Val[i] = Record.val;
            Record = Record.next;
        }
        
        //第三次周遊，是用來反轉的
        ListNode Reverse = head;
        for(int j = n-1; j >= 0; j--){
            Reverse.val = Val[j] ;
            Reverse = Reverse.next;
        }
        
        return head;
    }
}
           

  這是完全利用數組，那麼如何治隻利用連結清單呢？

  My solution(2): 疊代

   如果是雙連結清單，進行reverse是非常簡單的，是以我們可以借鑒雙連結清單的方法來反轉連結清單。這裡我們需要三個node, pre , cur, next 分别代表目前，之前和之後的node.

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode pre = null;
        ListNode next = null;
        
        
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        
        return pre;
        
    }
}
           

  My solution(3): 遞歸

  利用遞歸！

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        ListNode cur = head.next;
        ListNode res = reverseList(cur); //res是得到head之後的反轉
        
        head.next = null;
        cur.next = head;
        return res;      
        
    }
}
           

  接下來我們看看leetcode的234題。

  Pro:

Given a singly linked list, determine if it is a palindrome.

Follow up:Could you do it in O(n) time and O(1) space?

  My solution(1):

  建立了一個數組，如果是回行文，順着的和逆的應該相等。

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        
        ListNode countNum = head;
        int count = 1; 
        while(countNum.next != null){
            countNum = countNum.next;
            count++;
        }
        
        ListNode copyVal = head;
        int[] copy = new int[count];
        for(int j = 0; j < count; j++){
            copy[j] = copyVal.val;
            copyVal = copyVal.next;
        }
        
        int i = count-1;
        while(i >= 0){
            if(copy[i] != head.val) return false;
            
            head = head.next;
            i--;
        }

       //這裡可以稍微改進一下
      /*
        int i = 0;
        while(i < count/2){
            if(copy[i] != copy[count-1-i]) return false;
            i++;
        }

      */
        return true;
        
    }
}
           

但是，這其實是不符合題目要求的，因為題目要求Could you do it in O(n) time and O(1) space?，因為建立了一個數組，空間複雜度是 O(n).

My solution(2): 

這是我想出來的第二個方法，但是是錯誤的！源于我對連結清單沒有更深刻的了解。我先上代碼，大家可以看一下！

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        
        ListNode cur = head;
        ListNode reverse = reverseNode(cur);
        while(head.next != null){
            if(head.val != reverse.val) return false;
            
            head = head.next;
            reverse = reverse.next;
        }
        if(head.val != reverse.val) return false;
        else{
            return true;
        } 
            
        
    }
    private ListNode reverseNode(ListNode cur){
        if(cur == null || cur.next == null ) return cur;
        
         
        ListNode next = cur.next;
        ListNode res = reverseNode(next);
        
        cur.next = null;
        next.next = cur;
        return res;   
    }
}
           

  高手肯定立馬看出來了！！我至始至終都是在對這一個連結清單操作。比如，剛開始連結清單時[1,2,3,1], head指着第一個元素，reverse變成[1,3,2,1], head指向最後一個元素，reverse指向第一個元素.....是以不對。

  My solution(3):

To think about :Could you do it in O(n) time and O(1) space?如何不使用額外的空間，在連結清單本身上操作，來判斷是否相等

反轉連結清單法，連結清單前半段原地翻轉，再将前半段和後半段依次比較，判斷是否相等。

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        
        ListNode countNum = head;
        int count = 0;
        while(countNum != null){
            countNum = countNum.next;
            count++;
        }
        
        int middle = count/2;
        ListNode cur = head;
        ListNode pre = null;
        ListNode next = null;
        
        for(int i = 0; i < middle; i++){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        if(count% 2 == 1){
            cur = cur.next;
        }
        
        for(int j = 0; j < middle; j++){
            if(pre.val != cur.val) return false;
            
            else{
                pre = pre.next;
                cur = cur.next;
            }
        }
        return true;
    }
}
           

  我對這個解決方案不太滿意，因為感覺還是用了跟數組有關的東西，并沒有直接在連結清單上下手，比如如何得到中間的node? 我們需要知道整個連結清單中的元素，然後在判斷中間的元素在哪裡。

   My solution(4):

   先看一下代碼，然後在一一分析。

public class Solution {
    public boolean isPalindrome(ListNode head) {
       if(head == null || head.next == null) return true;
        
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast != null){
            slow = slow.next;
        }
        
        slow = reverse(slow);
        fast = head;
        
        while(slow != null){
            if(slow.val != fast.val) return false;
            
            slow = slow.next;
            fast = fast.next;
        }
        
        return true;
    }
    
    private ListNode reverse(ListNode rev){
        ListNode pre = null;
        ListNode next = null;
        
        while(rev != null){
            next = rev.next;
            rev.next = pre;
            pre = rev;
            rev = next;
        }
        
        return pre;
    }
}
           

  在這裡說明一下：

1 怎麼樣确定slow已經到來的middle的位置？

 while(fast != null && fast.next != null){ 

//為什麼要判斷fast.next, 如果fast.next = null, fast.next.next就沒有意義了。

            fast = fast.next.next;

            slow = slow.next;

        }

2  我們會發現，連結清單中元素可能為奇數個也可能為偶數個

如果是偶數個：

1221 > 1      2    2     1   null

                      (s)          (f)

我們把slow之後的反轉，就變成兩個連結清單

  null < 2 < 1

               (s 頭指針)

  1 > 2

(head 頭指針) 

如果是奇數個：

12321 > 1    2   3    2    1

                      (s)       (f)

此時如果把slow之後的反轉，會變成:

3   <   2<   1

                (s)

和 1    >     2

    (h)

這樣就沒辦法比較head.val 和s.val

如果加上這個：

if(fast != null){

            slow = slow.next;

        }

如果是奇數個：

12321 > 1    2   3    2    1

                           (s)       

此時如果把slow之後的反轉，會變成:

   2<   1

         (s)

和 1    >     2

    (h)