Java 深入分析鏈表面試實例題目

更新時間：2022年03月23日 08:38:10 作者：K穩(wěn)重

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，本篇帶你通過兩個實例題目來深入探索

鏈表面試題一

判斷鏈表是否是回文結構。

問題描述：

兄弟們，看圖理解什么是鏈表的回文結構：

回文結構：正著讀12 -> 23 ->34,倒著讀12->23->34

奇數(shù)偶數(shù)都可以：

問題分析：

要判斷是不是回文結構，那么我們就要遍歷鏈表，一個從前往后走，一個從后往前走，對應的val值要相同，那么我們就必須修改鏈表的指向，這里就要用到快慢指針幫我們找到中間的節(jié)點，從中間節(jié)點開始改變指向，指向變更完成之后再開始遍歷。

問題講解：

第一步：為了確保始終能找到我們的鏈表，定義一個head變量一直指向頭節(jié)點。

第二步：定義兩個變量，開始都指向head，通過快慢指針的方法求出中間節(jié)點。

第三步：定義一個cur變量指向中間節(jié)點的后面一個節(jié)點，讓cur變量來修改指向。

第四步：定義一個curNext變量等于cur.Next,防止改變指向后無法找到后面的節(jié)點。

代碼實現(xiàn)：

  public boolean chkPalindrome(ListNode head) {
        if(head == null) return false;//判斷一下鏈表是不是空，空的話直接返回false
        ListNode fast = head;//快指針fast，初始等于head
        ListNode slow = head;//慢指針slow，初始等于head
        while(fast != null && fast.next != null){//如果鏈表是奇數(shù)，fast.next == null停下，如果鏈表是偶數(shù)fast == null停下
            fast = fast.next.next;//fast走兩步
            slow = slow.next;//slow走一步
 
        }
        ListNode cur = slow.next;//cur等于slow的下一個節(jié)點
        while(cur != null){//cur不為空開始反轉(zhuǎn)
            ListNode curNext = cur.next;//curNext等于cur的下一個節(jié)點
            cur.next = slow;//開始反轉(zhuǎn)
            slow = cur;//反轉(zhuǎn)完了后讓slow等于cur
            cur = curNext;//cur再往后走一步。
        }
        while(head != slow){//判斷是不是回文結構
            if(head.val != slow.val){//不是回文結構
                return false;
            }
            if(head.next == slow){//偶數(shù)鏈表的情況
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

鏈表面試題二

輸入兩個鏈表，找出它們的第一個公共結點。

問題描述：

問題分析：

判斷：

1.如果兩個鏈表是相交那么是Y還是X形狀？ Y

2.如果兩個鏈表相交，值val域相同還是next域相同? next域相同

上圖就是相交的鏈表。

問題講解：

第一步：先定義兩個字節(jié)變量分別指向兩個鏈表的頭，headA和headB。

第二步：定義兩個變量求出兩條鏈表的差值。

第三步：再定義兩個字節(jié)變量ps和pl分別指向headA和headB。

第四步：讓長的鏈表先走他們的差值步。

第五步：兩個鏈表再一起走。

第六步：當ps=pl的時候就是共同節(jié)點了。

代碼實現(xiàn)：

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headB == null || headA == null) return null;//判斷其中一條鏈表的頭節(jié)點為空就是沒有焦點
        ListNode ps = headA;
        ListNode pl = headB;
        int lenA = 0;
        int lenB = 0;
        while(ps != null){求出ps鏈表的長度
            lenA++;
            ps = ps.next;
        }
        ps = headA;//讓ps重新等于頭節(jié)點
        while(pl != null){求出pl鏈表的長度
            lenB++;
            pl = pl.next;
        }
        pl = headB;//讓pl重新等于頭節(jié)點
        int len = lenA - lenB;
        if(len < 0){//判斷ps長還是pl長
            ps = headB;
            pl = headA;
            len = lenB - lenA;
        }
         while(len != 0)//求兩條鏈表的差值
                ps = ps.next;
                len--;
 
            }
        while(ps != pl){
            
            ps = ps.next;
            pl = pl.next;
        }
        return ps;
    }

到此這篇關于Java 深入分析鏈表面試實例題目的文章就介紹到這了,更多相關Java 鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: