目錄

• 基本性質(zhì)
• 鏈表的分類
  • 按連接方向分類
  • 按照有無循環(huán)分類
• 鏈表問題代碼實現(xiàn)的關(guān)鍵點
• 鏈表插入和刪除的注意事項
• 鏈表翻轉(zhuǎn)
• 向一個有序的環(huán)境鏈表中插入一個節(jié)點氓侧，并保持依舊有序
• 對于一個單鏈表，在不給定head的情況下刪除指定node导狡。要求時間復(fù)雜度O(1)
• 給定一個鏈表约巷，與一個數(shù)組num。要求實現(xiàn)荷蘭國旗
• 給定兩個有序鏈表的head旱捧，打印共同部分
• 給定一個單鏈表的head独郎，實現(xiàn)一個調(diào)整鏈表的函數(shù)，使得每K個節(jié)點之間逆序枚赡，如果最后不足K個氓癌，則不調(diào)整
• 判斷一個鏈表是否為回文結(jié)構(gòu)
• 判斷一個單鏈表是否有環(huán)，如有則返回入環(huán)節(jié)點贫橙。時間復(fù)雜度O(N)贪婉，額外空間復(fù)雜度O(1)
• 兩個無環(huán)單鏈表是否相交，時間復(fù)雜度O(N+M)料皇，額外空間復(fù)雜度O(1)
• 判斷兩個有環(huán)單鏈表是否相交谓松，時間復(fù)雜度O(N+M)星压，額外空間復(fù)雜度O(1)
• 判斷兩個鏈表是否相交践剂，并返回第一個相交的節(jié)點

基本性質(zhì)

• 鏈表問題算法難度不高，但考察代碼的實現(xiàn)能力

• 鏈表和數(shù)組一樣娜膘，都是一種線性結(jié)構(gòu)

1. 數(shù)組是物理地址上一段連續(xù)的存儲空間逊脯。
   可以通過下標(biāo)直接獲取元素
   當(dāng)內(nèi)容超出容量時需要重新定義數(shù)組。
2. 鏈表空間不一定保持聯(lián)系竣贪，為臨時分配的军洼。
   只能從鏈表的頭部開始一個一個查找
   增刪的效率高于數(shù)組，因為不需要更改內(nèi)存結(jié)構(gòu)

鏈表的分類

• 按連接方向分類

1. 單鏈表
   每個節(jié)點只能通過next指針演怎，指向下一個節(jié)點匕争。
2. 雙鏈表
   除了next指針之外，還有一個prev指針指向其上一個節(jié)點爷耀。

• 按照有無循環(huán)分類

1. 普通鏈表
   頭無prev甘桑，尾無next。

2. 循環(huán)鏈表
   首尾相接的鏈表。
   最后一個節(jié)點的next指針指向其第一個節(jié)點
   對于雙鏈表跑杭，其第一個節(jié)點的prev指針指向最后一個節(jié)點铆帽。

   
   

鏈表問題代碼實現(xiàn)的關(guān)鍵點

• 鏈表調(diào)整函數(shù)的返回值，往往是節(jié)點類型

鏈表在調(diào)整過程中往往遇到改變頭部的情況德谅，如果頭節(jié)點被改變則需要返回一個新頭部爹橱。

• 在調(diào)整鏈表的過程中，先采用畫圖的方式理清邏輯

注意那些指針變化了窄做，同時注意對前后節(jié)點的影響愧驱。

• 邊界條件的處理

頭節(jié)點，尾節(jié)點浸策，空節(jié)點的特殊處理冯键。

鏈表插入和刪除的注意事項

• 特殊處理鏈表為空或長度為1

• 插入過程的調(diào)整

取得前后節(jié)點，將前節(jié)點的next指向新節(jié)點庸汗，新節(jié)點的next指向后節(jié)點惫确。

• 刪除過程的調(diào)整

取得前后節(jié)點，將前一個節(jié)點的next指針指向后一個節(jié)點蚯舱。

• 頭尾插入或刪除

在邏輯的設(shè)計上應(yīng)該考慮空節(jié)點的情況

鏈表翻轉(zhuǎn)

• 特殊處理鏈表為空或長度為1

• 單鏈表的翻轉(zhuǎn)

已翻轉(zhuǎn)的頭節(jié)點head改化，下一個節(jié)點now

1. 將now節(jié)點的next指向head
2. 將now節(jié)點設(shè)置為已翻轉(zhuǎn)部分的新head

需要注意在執(zhí)行1，2步驟之前需要一個變量來儲存原now節(jié)點的next節(jié)點枉昏。
步驟2設(shè)置了新的head之后陈肛，將該節(jié)點作為新的now，繼續(xù)翻轉(zhuǎn)。

向一個有序的環(huán)境鏈表中插入一個節(jié)點蜡感，并保持依舊有序争占。

要求時間復(fù)雜度O(N)，額外空間復(fù)雜度O(1)谈撒。

• 如果鏈表為空

讓新節(jié)點node自己成為環(huán)形鏈表，并返回node即可匾南。

• 如果鏈表不為空

令變量prve設(shè)為頭節(jié)點啃匿，current設(shè)為第二個節(jié)點，兩個節(jié)點同步移動蛆楞。

• 當(dāng)有node<=prve && node>=current溯乒，則說明node應(yīng)該插入二者之間
  

• 若prve回到head但依舊沒有合適的位置插入
  說明node為最大值或最小值，插入head之前即可豹爹。
  需要區(qū)分為兩種情況下是否出現(xiàn)新的head裆悄，并返回。

對于一個單鏈表臂聋，在不給定head的情況下刪除指定node光稼。要求時間復(fù)雜度O(1)

• 如果node.next不為空崖技，也就是node不是尾節(jié)點

如果工程允許，可以將node.next的內(nèi)容copy到node節(jié)點上钟哥，變相的刪除了node節(jié)點的數(shù)據(jù)迎献。

• 如果node是尾節(jié)點

無法刪除

給定一個鏈表，與一個數(shù)組num腻贰。要求實現(xiàn)荷蘭國旗

• 將鏈表遍歷成數(shù)組吁恍，然后進(jìn)行荷蘭國旗排序，最后還原成鏈表播演。

• 遍歷鏈表的過程中使用三個小鏈表冀瓦。小于，等于写烤，大于翼闽。最后將三個鏈表串聯(lián)。

給定兩個有序鏈表的head洲炊，打印共同部分

• 有一個為空直接返回

• 采用外排的方式感局，直到有一個為空則停止。

給定一個單鏈表的head暂衡，實現(xiàn)一個調(diào)整鏈表的函數(shù)询微，使得每K個節(jié)點之間逆序，如果最后不足K個狂巢，則不調(diào)整撑毛。

1. 鏈表為空，長度<k或者k<2
   直接返回

• 通過棧結(jié)構(gòu)唧领，實現(xiàn)逆序

1. 需要保留上次逆序的最后一位元素藻雌，修改其next。
2. 最后段不足k個斩个，直接不修改胯杭。值將上次逆序的最后一個元素next設(shè)置好。
3. 第一組的第一個節(jié)點為頭節(jié)點萨驶。

• 不使用棧結(jié)構(gòu)歉摧，手動逆序

判斷一個鏈表是否為回文結(jié)構(gòu)

1. 將鏈表節(jié)點依次入棧艇肴，在彈出時與原鏈表依次比對腔呜。

2. 使用快行指針，通過二倍速的方式遍歷再悼。依次將慢指針的節(jié)點壓入棧中核畴，當(dāng)快節(jié)點遍歷到末尾時，慢指針正好處于中間位置冲九。
   繼續(xù)移動慢指針谤草，并與棧中彈出的元素做對比跟束。(需要注意總量的奇偶)

   
   

3. 將后半部分鏈表進(jìn)行逆序處理，從兩端同時進(jìn)行遍歷比對

   
   

判斷一個單鏈表是否有環(huán)丑孩，如有則返回入環(huán)節(jié)點冀宴。時間復(fù)雜度O(N)，額外空間復(fù)雜度O(1)

• 1. 如果鏈表有結(jié)尾温学，則說明無環(huán)

• 2.1 如果不要求額外空間復(fù)雜度略贮，可以直接用哈希表比對。

• 2.2 使用快行指針的方式

如果兩指針相遇則表示有環(huán)仗岖，此時將快指針改為1逃延，并從head重新同步移動，相遇處即為入環(huán)位置或者還有另一個證明轧拄。

• 代碼

/// 獲取入環(huán)節(jié)點
///
/// - Parameter node: 頭節(jié)點
/// - Returns: 有環(huán)則返回入環(huán)節(jié)點揽祥，否則返回空
func getLoopNode(head : Node) -> Node {
    //鏈表長度為 0，1檩电，2 不可能成環(huán)
    if head==nil || head.next==nil || head.next.next==nil {
        return nil
    }
    
    var slowP = head //慢行指針
    var fastP = head //快行指針
    
    while slowP != fastP {
        if slowP.next==nil || fastP.next.next==nil {  //鏈表有結(jié)尾拄丰，不可能成環(huán)
            return nil
        }
        slowP = slowP.next
        fastP = fastP.next.next
    }//運行到這里說明兩指針相遇了
    
    
    //從head開始遍歷再次相交則為入環(huán)點
    fastP = head
    while fastP != slowP {
        slowP = slowP.next
        fastP = fastP.next
    }
    
    return fastP
}

兩個無環(huán)單鏈表是否相交，時間復(fù)雜度O(N+M)俐末，額外空間復(fù)雜度O(1)

• 1. 先遍歷兩個鏈表確定長度

• 2. 若兩個鏈表結(jié)尾不同愈案，則不相交

• 3. 另長鏈表從短鏈表開始位置與短鏈表再次同步遍歷，查看是否相同鹅搪。

• 代碼

/// 兩個無環(huán)單鏈表是否相交
///
/// - Parameters:
///   - head1: 鏈表1
///   - head2: 鏈表2
/// - Returns: 相交點或者為空
func noLoop(head1:Node ,head2:Node) -> Node {
    
    if head1==nil || head2==nil {
        return nil
    }
    var p1 = head1
    var p2 = head2
    
    //獲取兩個鏈表長度差值
    var n = 0
    while p1.next != nil {
        p1 = p1.next
        n+=1
    }
    while p2.next != nil {
        p2 = p2.next
        n-=1
    }
    
    if p1 != p2 { //若兩個鏈表結(jié)尾不同站绪，則一定不相交
        return nil
    }
    
    p1 = n>=0 ? head1:head2 //使 p1 指向較長的鏈表
    p2 = p2==head1 ? head2:head1 //使p2 指向另一個鏈表
    
    n = abs(n) //取絕對值
    while n>0 {//將長鏈表移動n次。
        p1 = p1.next
        n-=1
    }
    
    //查找鏈表上第一個相同的點
    while p1 != p2 {
        p1 = p1.next
        p2 = p2.next
    }
    
    return p1
}

判斷兩個有環(huán)單鏈表是否相交丽柿，時間復(fù)雜度O(N+M)恢准，額外空間復(fù)雜度O(1)

首先都需要先去定單獨的入環(huán)節(jié)點，然后

1. 是否入環(huán)之前已經(jīng)相交

   
   

2. 是否入環(huán)時才相交甫题，則入環(huán)位置節(jié)點相同

   
   
   
   

   如果相交點為loop1或者loop2馁筐，則為入環(huán)時才相交

3. 入環(huán)后才相交
   循環(huán)其中一個環(huán)，若遇到另一個的入環(huán)節(jié)點則返回坠非。

   
   

4. 否則敏沉，兩鏈表并未相交

• 代碼

/// 兩個有環(huán)單鏈表是否相交
///
/// - Parameters:
///   - head1: 鏈表1
///   - head2: 鏈表2
///   - loop1: 鏈表1入環(huán)點
///   - loop2: 鏈表2入環(huán)點
/// - Returns: 相交點或者為空
func bothLoop(head1:Node ,head2:Node ,loop1:Node ,loop2:Node) -> Node {
    
    if head1==nil || head2==nil{
        return nil
    }
    
    if loop1 == loop2 { //兩個鏈表在入環(huán)之前已經(jīng)相交
        var p1 = head1
        var p2 = head2
        
        //獲取兩個鏈表長度差值
        var n = 0
        while p1.next != loop1 {
            p1 = p1.next
            n+=1
        }
        while p2.next != loop2 {
            p2 = p2.next
            n-=1
        }
        
        p1 = n>=0 ? head1:head2 //使 p1 指向較長的鏈表
        p2 = p2==head1 ? head2:head1 //使p2 指向另一個鏈表
        
        n = abs(n) //取絕對值
        while n>0 {//將長鏈表移動n次。
            p1 = p1.next
            n-=1
        }
        
        //查找鏈表上第一個相同的點
        while p1 != p2 {
            p1 = p1.next
            p2 = p2.next
        }
        
        return p1
    }else { //兩個鏈表在入環(huán)之后才相交
        var p1 = loop1.next
        var p2 = loop2
        while p1 == loop1 { //循環(huán)loop1一次
            p1 = p1.next
            if p1 == p2 {
                return p1
            }
        }
        return nil  //并未相交
    }
}

判斷兩個鏈表是否相交炎码，并返回第一個相交的節(jié)點

1. 嘗試找到各自的入環(huán)節(jié)點

2. 若一個有環(huán)一個無環(huán)盟迟，則不相交

3. 若都為無環(huán)，則按照上文《兩個無環(huán)單鏈表是否相交》的方式查找

4. 若都為有環(huán)潦闲，則按照上文《判斷兩個有環(huán)單鏈表是否相交》的方式查找

• 代碼

func getIntersectNode(head1:Node,head2:Node) -> Node {
    if head1 == nil || head2 == nil {
        return nil
    }
    
    //獲取兩個入環(huán)節(jié)點
    var loop1 = getLoopNode(head: head1)
    var loop2 = getLoopNode(head: head2)
    
    if (loop1 == nil && loop2 != nil)||(loop1 != nil && loop2==nil) {
        return nil //一個有環(huán)一個無環(huán)攒菠，肯定不相交
    }
    
    if loop1==nil || loop2==nil {//兩個鏈表都不為環(huán)型結(jié)構(gòu)
        return noLoop(head1: head1, head2: head2)
    }else { //兩個環(huán)形鏈表
        return bothLoop(head1: head1, head2: head2, loop1: loop1, loop2: loop2)
    }
}

參考資料

左神牛課網(wǎng)算法課