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

1. 環(huán)形鏈表

給定一個鏈表宠能，判斷鏈表中是否有環(huán)淆院。

進階

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

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

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

圖1

但其實還有一種比較特殊一點的環(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會相遇
        */
        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. 合并兩個有序鏈表

將兩個有序鏈表合并為一個新的有序鏈表并返回泌辫。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的随夸。

示例：

輸入: 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;
        
        // 首先對比兩個鏈表頭部的值的大小，小的鏈表為最終返回的鏈表震放，即將頭部大的拆開插入小的鏈表
        if(l1.val <= l2.val){
            head = l1;
            p1 = l1;
            p2 = l2;
        }else{
            head = l2;
            p1 = l2;
            p2 = l1;
        }
        
        /**
        *  進入循環(huán)宾毒，當判斷p2指向的結(jié)點的值大于等于p1所指向且小于p1的下個結(jié)點的值時
        *  將p2所指向的結(jié)點插到p1之后，并將p1指向被插入的結(jié)點
        *  當p1或p2為最后一個結(jié)點時跳出循環(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;
            }
        }
        
        /**
        *  這時會有兩張情況：
        *  1. p2為最后一個結(jié)點殿遂，只需再進行一次循環(huán)诈铛，將p2插入鏈表
        *  2. p1為最后一個結(jié)點邪锌，說明鏈表的最大的值都沒有比p2所指向的結(jié)點的值大，只需將p2插到鏈表的最后即可
        *     因為這時p1指向的是最后一個結(jié)點癌瘾，所以直接 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é)：

這題第一次做的時候思路很亂觅丰，做了一個晚上都沒做出來，第二天再做的時候理清思路10分鐘就做出來了妨退，事實證明做題思路很重要

3. 總結(jié)

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

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