記錄一下最近刷的比較有意思的題

1. 環(huán)形鏈表

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

進(jìn)階

你能否不使用額外空間解決此題？

我的思路與解答（1ms）：

首先理解環(huán)形鏈表的概念，我開始以為只有一種，就是頭尾相連的鏈表就是環(huán)形鏈表，如下圖；

圖1

但其實(shí)還有一種比較特殊一點(diǎn)的環(huán)形鏈表，如下圖；

圖2

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        /** 
        *  主要思路：用雙指針解法，slow和fast，都從頭部開始
        *  slow每次走一步，fast每次走兩步
        *  這樣不論是頭尾相連的環(huán)形鏈表還是特殊的環(huán)形鏈表
        *  在若干步后slow和fast會(huì)相遇
        */
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
            if(fast.next != null){
                fast = fast.next;
            }else{
                return false;
            }
            if(slow.equals(fast)){
                return true;
            }
        }
        return false;
    }
}

小結(jié)：

一開始只想到了頭尾相連的鏈表，去搜索了相關(guān)概念后才知道原來還有另一種，但是這題做起來思路還是比較明確。

2. 合并兩個(gè)有序鏈表

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

輸入: 1->2->4, 1->3->4
輸出: 1->1->2->3->4->4

我的思路與解答（11 ms）：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head;
        ListNode p1;
        ListNode p2;
        ListNode temp;
        
        // 首先對比兩個(gè)鏈表頭部的值的大小，小的鏈表為最終返回的鏈表，即將頭部大的拆開插入小的鏈表
        if(l1.val <= l2.val){
            head = l1;
            p1 = l1;
            p2 = l2;
        }else{
            head = l2;
            p1 = l2;
            p2 = l1;
        }
        
        /**
        *  進(jìn)入循環(huán)，當(dāng)判斷p2指向的結(jié)點(diǎn)的值大于等于p1所指向且小于p1的下個(gè)結(jié)點(diǎn)的值時(shí)
        *  將p2所指向的結(jié)點(diǎn)插到p1之后，并將p1指向被插入的結(jié)點(diǎn)
        *  當(dāng)p1或p2為最后一個(gè)結(jié)點(diǎn)時(shí)跳出循環(huán)
        */ 
        while(p1.next != null && p2.next != null){
            if(p2.val >= p1.val) {
                if(p1.next.val > p2.val) {
                    temp = p1.next;
                    p1.next = p2;
                    l2 = p2.next;
                    p2.next = temp;
                    p1 = p2;
                    p2 = l2;
                    continue;
                }
                p1 = p1.next;
            }
        }
        
        /**
        *  這時(shí)會(huì)有兩張情況：
        *  1. p2為最后一個(gè)結(jié)點(diǎn)，只需再進(jìn)行一次循環(huán)，將p2插入鏈表
        *  2. p1為最后一個(gè)結(jié)點(diǎn)，說明鏈表的最大的值都沒有比p2所指向的結(jié)點(diǎn)的值大，只需將p2插到鏈表的最后即可
        *     因?yàn)檫@時(shí)p1指向的是最后一個(gè)結(jié)點(diǎn)，所以直接 p1.next = p2 即可
        */
        if(p2.next == null){
            while(p1.next != null){
                if(p2.val >= p1.val){
                    if(p1.next.val > p2.val) {
                        temp = p1.next;
                        p1.next = p2;
                        l2 = p2.next;
                        p2.next = temp;
                        p1 = p2;
                        p2 = l2;
                        return head;
                    }
                    p1 = p1.next;
                }
            }
        }
        
        if(p1.next == null){
            p1.next = p2;
        }
        
        return head;
        
    }
}

小結(jié)：

這題第一次做的時(shí)候思路很亂，做了一個(gè)晚上都沒做出來，第二天再做的時(shí)候理清思路10分鐘就做出來了，事實(shí)證明做題思路很重要

3. 總結(jié)

鏈表類的題目尤其需要思路明確，有一點(diǎn)錯(cuò)誤就容易發(fā)生空指針異常。

本文作者：RoNnx
博客鏈接：http://ronnx.top/2018/06/17/20180004/
版權(quán)聲明：本作品采用「知識(shí)共享署名-非商業(yè)性使用-相同方式共享 4.0 國際許可協(xié)議 進(jìn)行許可」,轉(zhuǎn)載請注明出處！