// 鏈表節(jié)點(diǎn)
class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

// 鏈表
class List {
    var head: ListNode?
    var tail: ListNode?
    
    // 尾插法
    func appendToTail(_ val:Int) {
        if tail == nil {
            tail = ListNode(val)
            head = tail
        } else {
            tail!.next = ListNode(val)
            tail = tail!.next
        }
    }
    
    // 頭插法
    func appendToHead(_ val:Int) {
        if head == nil {
            head = ListNode(val)
            tail = head
        } else {
            let tmp = ListNode(val)
            tmp.next = head
            head = tmp
        }
    }
}

算法題一：

給出一個(gè)鏈表和一個(gè)值X策州，要求將鏈表中所有小于X的值放到左邊埠褪，所有大于等于X的值放到右邊浓利，并且原鏈表的節(jié)點(diǎn)順序不能變

思路：

先處理左邊（比x小的節(jié)點(diǎn)）,然后再處理右邊（比x大的節(jié)點(diǎn)）,最后再把左右兩邊連起來(lái)。

func partition(_ head: ListNode?, _ x:Int) -> ListNode? {
        let prevDummy = ListNode(0), postDummy = ListNode(0)
        var prev = prevDummy, post = postDummy
        
        var node = head
        
        while node != nil {
            if node!.val < x {
                prev.next = node
                prev = node!
            } else {
                post.next = node
                post = node!
            }
            
            node = node?.next
        }
        
        // 防止構(gòu)成環(huán)
        post.next = nil
        
        // 左右兩部分相連
        prev.next = postDummy.next
        
        return prevDummy.next
    }

前面提到了環(huán)钞速，怎么檢測(cè)鏈表中是否有環(huán)存在贷掖？

算法題二：快慢指針

如何檢測(cè)一個(gè)鏈表中是否有環(huán)

思路：

用兩個(gè)指針同時(shí)訪問(wèn)鏈表，其中一個(gè)的速度是另一個(gè)的兩倍渴语，如果它們變成相等了苹威，那么這個(gè)鏈表就有環(huán)了，

    func hasCycle(_ head:ListNode?) -> Bool {
        var slow = head
        var fast = head
        
        while fast != nil && fast!.next != nil {
            slow = slow!.next
            fast = fast!.next!.next
            
            // 引用類型判斷相等用 === 驾凶，值類型用 == 
            if slow === fast {
                return true
            }
        }
        return false
    }

算法題三：

刪除鏈表中倒數(shù)第n個(gè)節(jié)點(diǎn)牙甫，例：1->2->3->4->5, n=2,返回 1->2->3->5
注意：給定n的長(zhǎng)度小于等于鏈表的長(zhǎng)度

思路：

依然是快行指針，這次兩個(gè)指針移動(dòng)速度相同调违。但是一開(kāi)始窟哺，第一個(gè)指針（在指向頭結(jié)點(diǎn)之前）就落后第二個(gè)指針n個(gè)節(jié)點(diǎn)。接著兩者同時(shí)移動(dòng)技肩，當(dāng)?shù)诙€(gè)指針移動(dòng)到尾節(jié)點(diǎn)時(shí)且轨，第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)就是我們要?jiǎng)h除的節(jié)點(diǎn)。

func removeNthFromEnd(_ head:ListNode?,_ n:Int) ->ListNode? {
        
        guard let head = head else {
            return nil
        }
        
        let dummy = ListNode(0)
        dummy.next = head
        
        var prev:ListNode? = dummy
        var post:ListNode? = dummy
        
        for _ in 0 ..< n {
            if post == nil {
                break
            }
            post = post!.next
        }
        
        while post != nil && post!.next != nil {
            prev = prev!.next
            post = post!.next
        }
        
        // 刪除節(jié)點(diǎn)
        prev!.next = prev!.next!.next
        
        return dummy.next
    }