(二) 連結串列 – 經典問題彙總

NO IMAGE

(一)找到連結串列的倒數第n個節點

    1.這個問題不難,我們可以兩次遍歷連結串列,第一遍記錄連結串列的長度L,第二遍從頭遍歷連結串列,找到L-n 1的位置的節點,然後輸出,這樣時間複雜度為o(n),空間複雜度為o(1)

    2.上面的方法看起來不錯,但是我們還可以有更好的方法,我們僅僅使用一次遍歷就可以,我們使用兩個指標slowNode和fastNode來一起遍歷,兩個指標都指向連結串列頭結點,僅當fastNode移動了n個節點的時候,slowNode才開始移動,然後兩個指標同時移動直到fastNode到達連結串列末尾,這個時候slowNode所指向的節點就是倒數第n個節點,時間複雜度O(n),空間複雜度o(1)

public ListNode NthNodeFromEnd(ListNode headNode, int k){
        ListNode slowNode = headNode;
        ListNode fastNode = headNode;
        for(int j = 1; j<k; j  ){
            //錯誤處理,當引數大於連結串列元素個數時
            if(fastNode == null||fastNode.getNext() == null){
                System.out.println("引數不正確");
                return null;
            }
            fastNode = fastNode.getNext();
        }
        while(fastNode.getNext()!=null){
            fastNode = fastNode.getNext();
            slowNode = slowNode.getNext();
        }
        return slowNode;
    }

    (二)判斷連結串列是以NULL結尾還是形成一個環

    1.一個直接的判定方法是從第一個節點開始,令其為當前節點,看看後面是否存在節點的後繼節點等於當前節點,如果存在這樣的節點就說明存在環,如果不存在則對連結串列中的其他節點重複上述操作。但是這樣不僅複雜,如果處理不好還容易出現死迴圈。

    2.一個簡單有效的方法是由floyd提出來的,,該方法被稱為floyd環判定演算法,該方法使用連結串列中移動速度不同的兩個指標,一旦他們進入環就會相遇,即表示存在環,這個判定方法的正確性在於,快速移動指標和慢速移動指標將會指向同一位置的唯一可能情況,就是整個或部分連結串列是一個環。時間複雜度O(n),空間複雜度O(1)

public Boolean DoesLinkedListContainsLoop(ListNode headNode){
ListNode fastNode = headNode;
ListNode slowNode = headNode;
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
return true;
}
}
return false;
}

(三)判定連結串列當中是否存在環,如果存在找到環的起始節點

    這是問題二的擴充套件,首先判斷是否存在環,如果存在環,則在fastNode與slowNode相遇之後,初始化slowNode使其等於頭結點,然後slowNode與fastNode從各自位置沿著連結串列移動,每次移動一個節點,他們再次相遇的位置就是環開始的位置,我們也可以用這種方法來刪除環。

    假設起點到環的起點距離為m,已經確定有環,環的周長為n,(第一次)相遇點距離環的起點的距離是k。那麼當兩者相遇時,慢指標移動的總距離為i,i = m a * n k,因為快指標移動速度為慢指標的兩倍,那麼快指標的移動距離為2i,2i = m b * n k。其中,a和b分別為慢指標和快指標在第一次相遇時轉過的圈數。我們讓兩者相減(快減慢),那麼有i = (b – a) * n。即i是圈長度的倍數。利用這個結論我們就可以理解Floyd解法為什麼能確定環的起點。將一個指標移到連結串列起點,另一個指標不變,即距離連結串列起點為i處,兩者同時移動,每次移動一步。當第一個指標前進了m,即到達環起點時,另一個指標距離連結串列起點為i m。考慮到i為圈長度的倍數,可以理解為指標從連結串列起點出發,走到環起點,然後繞環轉了幾圈,所以第二個指標也必然在環的起點。即兩者相遇點就是環的起點。

public ListNode FindBiginOfLoop(ListNode headNode){
Boolean loopExists = false;
ListNode fastNode = headNode;
ListNode slowNode = headNode;
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
loopExists = true;
break;
}
}
if(loopExists){
slowNode = headNode;
while(true){
if(slowNode == fastNode){
return slowNode;
}
slowNode = slowNode.getNext();
fastNode = fastNode.getNext();
}
}else{
System.out.println("不存在環");
return null;
}
}

(四)判斷連結串列當中是否存在環,如果存在返回環的長度

        嗯,還是第二個問題的延伸,如果存在環的話,記錄slowNode當時指向的節點,然後繼續讓slowNode每次移動一步,直到再次到達記錄的位置就可以計算出環的長度

public int FindLoopLength(ListNode headNode){
Boolean loopExists = false;
ListNode fastNode = headNode;
ListNode slowNode = headNode;
while(fastNode.getNext()!=null && fastNode.getNext().getNext()!=null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
if(slowNode == fastNode){
loopExists = true;
break;
}
}
if(loopExists){
int count = 1;
while(slowNode.getNext()!= fastNode){
slowNode = slowNode.getNext();
count  ;
}
return count;
}else{
return 0;
}
}

(五)在有序連結串列中插入一個新的節點

    遍歷連結串列,找到合適的位置插入連結串列節點,要注意插入到連結串列頭結點時要做一些處理

public ListNode InsertInSortedList(ListNode headNode, ListNode NewNode){
ListNode currentNode = headNode;
ListNode tempNode = null;
if(headNode == null) return NewNode;
if(currentNode.getData() >= NewNode.getData()){
NewNode.setNext(currentNode);
return NewNode;
}
while(currentNode!=null && currentNode.getData()<NewNode.getData()){
tempNode = currentNode;
currentNode = currentNode.getNext();
}
NewNode.setNext(currentNode);
tempNode.setNext(NewNode);
return headNode;
}

(六)逆置單向連結串列

        遍歷連結串列,將連結串列方向反轉即可,但是注意,原來連結串列頭部節點,反轉後要指向null;時間複雜度為o(n),空間複雜度為O(1)

public ListNode ReverseList(ListNode headNode){
ListNode tempNode = null;
ListNode nextNode = null;
while(headNode!=null){
nextNode = headNode.getNext();
headNode.setNext(tempNode);
tempNode = headNode;
headNode = nextNode;
}
return tempNode;
}

(七)假設兩個連結串列在某個節點相交後成為一個單向連結串列,兩個連結串列頭結點是已知的,相交節點未知,求出連結串列相交的節點

     1. 將兩個連結串列分別放到棧裡,然後同步出棧,最後一個相等的節點就是相交節點,這個比較簡單,時間複雜度為o(max(m,n))

空間複雜度為O(m n)

    2.   可以先分別遍歷原來連結串列,計算連結串列長度,求出連結串列長度的差d,長連結串列先走d步,然後長連結串列和短連結串列一起向後遍歷,出現的第一個相等的位元組就是連結串列相交的地方,時間複雜度為O(max(m,n)),空間複雜度為O(1),比前一種做法空間複雜度低

public  ListNode FindIntersectingNode(ListNode list1, ListNode list2){
int length1 = ListLength(list1);
int length2 = ListLength(list2);
ListNode Node1 = null , Node2 = null;
int diff = 0;
if(length1>length2){
Node1 = list1;
Node2 = list2;
diff = length1-length2;
}else{
Node1 = list2;
Node2 = list1;
diff = length2 - length1;
}
while(diff>0){
Node1 = Node1.getNext();
diff--;
}
while(Node1!=null){
if(Node1.getData()==Node2.getData()){
return Node1;
}
Node1 = Node1.getNext();
Node2 = Node2.getNext();
}
return null;
}

(八)如何找到連結串列的中間節點

        1.遍歷一遍連結串列,返回連結串列長度n,再遍歷一遍找到n/2的位置,但是這樣需要遍歷兩遍連結串列

        2.使用兩個指標,一個快指標一個慢指標,快指標移動的速度是慢指標移動速度的兩倍,當快指標遍歷結束時慢指標的位置就是連結串列中間位置,當節點個數為奇數時四捨五入

public ListNode FindMiddle(ListNode headNode){
ListNode slowNode = headNode, fastNode = headNode;
if(ListLength(headNode)==0){
return null;
}
while(fastNode.getNext()!=null&&fastNode.getNext().getNext()!=null){
slowNode = slowNode.getNext();
fastNode = fastNode.getNext().getNext();
}
return slowNode;
}

(九)如何從表尾開始列印連結串列

        使用遞迴超級方便,空間複雜度O(n),時間複雜度為O(n)

public void PrintListFromEnd(ListNode headNode){
if(headNode == null)
return;
PrintListFromEnd(headNode.getNext());
System.out.println(headNode.getData());
}