1. 線性表反轉(zhuǎn)
2. 查找出奇數(shù)個元素的鏈表中間位置的結(jié)點
3. 判斷鏈表是否有環(huán)

1. 線性表反轉(zhuǎn)

前面已有一篇文章介紹線性表反轉(zhuǎn)的四種算法

2. 查找出奇數(shù)個元素的鏈表中間位置的結(jié)點

暴力解法：先通過一次遍歷去計算鏈表的長度并計算出中間位置，接著再通過一次遍歷去查找這個位置的數(shù)值腺晾。

巧妙解法：
利用快慢指針：定義兩個指針燕锥，一個快指針，一個慢指針悯蝉，其中快指針每次走兩步归形，而慢指針每次走一步。定義兩個指針fast和slow鼻由，開始時兩個指針都指向鏈表頭head暇榴，然后在每一步操作中slow向前走一步即：slow = slow->next，而fast每一步向前兩步即：fast = fast->next->next蕉世。過程如下：

C 語言實現(xiàn)如下：

// 查找出奇數(shù)個元素的鏈表中間位置的結(jié)點
Node* middle_value(Node* head){
    // 快指針蔼紧，每次步進為2
    Node* fast = head;
    // 快指針，每次步進為1
    Node* slow = head;
    
    // 由于總數(shù)是奇數(shù)個狠轻，當fast跳轉(zhuǎn)到最后一個時歉井，slow剛好為中間結(jié)點
    while (fast&&fast->next&&fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    return slow;
}

偽代碼如下：

while(fast && fast.next && fast.next.next){
    fast = fast.next.next;
    slow = slow.next;
}

3. 判斷鏈表是否有環(huán)

下圖便是一個循環(huán)鏈表

判斷鏈表是否有環(huán)依然可以通過快慢指針去實現(xiàn)。

由于fast要比slow移動的快哈误，如果有環(huán)哩至，fast一定會先進入環(huán)，而slow后進入環(huán)蜜自。當兩個指針都進入環(huán)之后菩貌，經(jīng)過一定步的操作之后，二者一定能夠在環(huán)上相遇重荠，并且此時slow還沒有繞環(huán)一圈箭阶，也就是說一定是在slow走完第一圈之前相遇。如果沒有環(huán)，最終會結(jié)束循環(huán)

C 語言實現(xiàn)如下：

// 判斷鏈表是否有環(huán)
int have_ring(Node* head)
{
    // 快指針仇参，每次步進為2
    Node* fast = head;
    // 快指針嘹叫，每次步進為1
    Node* slow = head;
    
    // 由于總數(shù)是奇數(shù)個，當fast跳轉(zhuǎn)到最后一個時诈乒，slow剛好為中間結(jié)點
    while (fast&&fast->next&&fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast) {
            return 1;
        }
    }
    
    return 0;
}

偽代碼如下：

while(fast && fast.next && fast.next.next){
    fast = fast->next->next;
    slow = slow->next;
    if(slow == fast) 
        return true;
}