一、移除鏈表元素

題目鏈接：

移除鏈表元素

那么根據題目的要求我們大致明白這道題要做什么，就是將一個鏈表中，和指定的值相等的元素的節點刪除，然后返回刪除后的新的鏈表，然后題目給我們傳入的參數是鏈表的頭節點和指定的元素。

解法一：

這里其實很多人學習了前面的單鏈表的實現的話，是很容易想到的，我們前面學習了，鏈表刪除指定節點的方法，還有查找指定元素的位置。剛剛好在這道題搭配使用，我們可以使用一個函數，將在這個函數中將這兩個函數調用，然后直到我們查找指定元素位置的函數返回值為空的時候，那么就說明這個鏈表中等于這個指定數據的節點已經刪除完了，那么就可以返回最新的鏈表了，如果不為空，那么我們就先進行刪除，然后再遞歸這個函數。

但是我們這么操作，就很容易造成堆棧，然后導致棧溢出，所以我們解這道題就不使用這個方法。

解法二：

在這道題中，其是要求返回新的鏈表的頭節點，并沒有要求在原來的鏈表上進行刪除，那么我們可以創建一個新的鏈表，然后遍歷原鏈表，不相等的元素，那么我們就進行尾插，不過要注意的是，這個新的鏈表在初始的時候，我們第一次進行尾插，那么此時要讓我們表示新鏈表的指針指向這個節點，然后那個往下走的指針也是，也要指向這個節點，然后在后續的尾插就讓另外一個指針進行變化即可，然后完成后，就返回這個頭節點即可。

我們提交看看：

我們通過測試用例來分析：

我們發現輸出的結果中，還是有最后一個6，那么這是為啥呢？

當pur走到最后一個節點的時候，那么此時，val不符合if的條件，那么其直接就走到了

pur=pur->next這個語句，然后循環結束，那么我們的新鏈表，再最后的5打印后，其實其5這個節點中，其指向下一節點的指針，還是指向著6這個節點，那么我們這個鏈表還是會包括6這個節點，所以我們在遍歷完后，一定要對尾節點指向下一個節點的指針置為空。

?那么我們對尾節點置空，又導致另外一個錯誤了，那就是當我們的原鏈表為空的時候，那么我們就對一個空指針進行解引用了，所以我們要使用一個if判斷當前的尾指針是否為空，如果不為空，那么我們才進行置空操作。

如下：

?可以看到我們這樣修改就通過了。

二、合并兩個有序鏈表?

題目鏈接：合并兩個有序鏈表

這個題目和我們上一篇中的合并兩個有序數組有點類似，這道題目就是其有兩個鏈表，然后兩個鏈表的元素都是按照升序的情況排序的，然后我們現在要將其合并到一個鏈表中，且這個新的鏈表也要為升序的情況。

我們前面在數組的情況下是使用兩個指針來完成的，那么這道題我們該如何解決呢？

那么這個題目沒有說不可以創建一個新的鏈表，那么我們可以創建一個新的鏈表，然后創建兩個指針，一個是src1指向第一個鏈表，一個src2指向第二個鏈表，然后對其每個節點進行遍歷且比較，小的就尾插到新的鏈表中。那么我們循環的條件是啥呢？

就是當其中一個鏈表已經遍歷完，其元素已經全部尾插到新的鏈表中的時候，那么此時的比較就可以結束了，然后剩下的沒尾插完的鏈表，我們再插入即可，但是我們此時就不在需要使用循環插入了，我們只需要指向其下一個節點即可。這樣就可以找到其剩余的節點了，而且尾節點也是指向空的。

方法如下：

提交看看：

?可以看到當鏈表1為空，鏈表2不為空的時候，那么此時就會出錯，那么我們的鏈表1為空，那么就直接到最后兩個if了，那么第一個if進不去，就到第二個了，然后此時的newlist就為空，那么我們此時是對一個空指針進行解引用了，那么就使得程序錯誤了。同理當鏈表2為空，鏈表1不為空也會出現這種錯誤。

所以這兩種情況我們要特殊處理。

?不過我們會發現上面的代碼會有很多重復進行的操作，那么我們有沒有上面辦法可以使得上面的代碼變得簡潔一些呢？

我們發現上面很多重復的動作都是因為一個特殊情況，就是鏈表為空的情況導致的。

那么我們可以在開始就創建一個鏈表，但是這個鏈表申請的時候是不存儲東西的，其頭節點是一個空的節點，那么我們就不在需要考慮鏈表為空的情況了，可以直接在這個鏈表進行為尾插的操作了，然后在最后我們將這個鏈表的頭節點的下一個節點返回即可。

不過這個空節點，是我們使用函數malloc申請的，那么我們在使用完后，要記得釋放掉，不然會造成空間的浪費，我們在釋放前就將其下一個節點先保存起來即可。

優化后：

三、反轉鏈表?

題目鏈接：反裝鏈表

?題目的要求就是要我們將一個鏈表反過來，就是其走的方向和原來的反過來，頭節點變為尾節點，尾節點變成頭節點

解法一：

我們很容易就可以想到的是，我們創建一個新的鏈表，然后我們遍歷原鏈表，然后將原鏈表的數據頭插到新的鏈表即可。

代碼如下：

?解法二：

解法二就是使用指針的方法，在原鏈表上進行操作，就直接對鏈表的指向進行修改。那么我們要如何進行修改呢？

我們創建三個指針n1，n2，n3，一個指向空，一個指向鏈表的頭節點，一個指向鏈表頭節點的下一個節點。

然后我們就讓這個頭節點的指向下一個節點的指針指向n1，也就是n2->next=n1，然后三個指針都往后走一個節點的位置，即n1=n2，n2=n3，n3=n3->next;那么我們再畫圖就可以知道，此時的n1是在頭節點的位置了，然后我們再讓n2->next=n1，那么就使得我們第二個節點指向下一個節點的指針指向的是頭節點了，那么此時是第二個節點指向第一個節點了，然后我們反復這樣操作，指到n2走到尾節點，然后再對這個尾節點進行修改，然后再走一步，那么此時n2就為空了，那么就不在需要修改了。那么此時就結束循環即可。

不過我們看到上面題目的測試用例，會發現有個是空表，因為我們知道我們對于一個空指針進行解引用是錯誤的，那么為了避免這種錯誤，我們對于傳入的是空鏈表的情況特殊處理一下。

那么走到最后，我們要返回的是新的鏈表的頭節點，那么此時n2是在新的頭節點的后面一個位置了，然后n1是在n2的前一個節點的位置的，那么此時n1的位置剛剛好就是反轉后的鏈表的頭節點。

還有就是，我們的循環條件是n2到空的時候，那么n3早就已經為空了，那么我們此時就不可以再對其解引用了，所以我們使用一個if進行處理。

代碼如下：

?四、鏈表的中間節點

題目鏈接：鏈表的中間節點

解法一：?

題目的描述也很簡單，就是有一個鏈表，讓我們找他中間的位置。然后如果是偶數個的節點，那么其中間節點就是兩個，那么我們取后面的一個。

那么我們很快就可以想到一個思路：

就是先讓這個鏈表進行遍歷，然后我們創建一個整型變量，記錄其遍歷的次數，那么就是這個鏈表的節點數，然后我們將這個節點數除2，那么就是我們的中間節點了。

比如：當前鏈表為三個節點，那么除二，就是1.5，然后我們是整型數據，那么其結果其實是1，那么就往下走一次就是中間的節點了，現在為4個節點，那么我們走兩次就到第三個節點，就是題目要求的那個節點了。

代碼如下：

?

解法二：

我們可以創建兩個指針，一個快指針，一個慢指針，我們要找的是中間節點，那么我們的慢指針就一次走兩步，慢指針就一次走一步，那么等到快指針走到尾的時候，那么就可以結束了，那么此時慢指針的位置就在鏈表的中間節點了，不過我們要注意的是。那么我們的循環條件就是當快指針走到尾的時候就結束循環，但是我們會發現，當鏈表的節點數為偶數的時候，那么此時我們的快指針是最后走到尾節點的時候，還會再往下走一步的，那么我們的快指針此時就為空了，那么此時就要停止循環了。然后奇數個的時候，那么此時我們的快指針就剛剛好在尾節點上，那么此時我們也應該結束循環了，那么此時我們循環結束的條件可以為->next，此時其下一個節點為空，剛剛好可以結束循環。

代碼如下：

?五、判斷鏈表是不是回文結構

題目鏈接：鏈表回文結構

前面我們對于數組，字符串，都有學習過回文結構，也實現過判斷其是否為回文結構，所以這里我們不過多介紹回文結構。

下面我們來解題

解法一：

我們如果先不理題目的要求，那么我們很快可以想到的是，遍歷鏈表，將鏈表的數據存儲到一個普通的數組中，然后就可以使用我們前面的方法進行判斷了。

但是我們的題目要求我們的空間復雜度為O(1)，那么我們如果這樣做的話，空間復雜度就為O(n)了，就不符合題目的要求了，但是我們再看題目的后面，其鏈表的長度小于等于900，那么我們一次給夠900個空間，那么空間復雜度不就是O(1)了嗎。

代碼如下：

我們知道上面的題目，其給出了這個鏈表的最大的長度，那么我們的空間直接給最大，那么其空間復雜度就直接為O(1)了，那么如果其并沒有給出這個情況的話，那么我們這么操作是達不到要求的。那么我們下面看一個可以達到要求的解法。?

解法二：

我們鏈表不能直接進行比較就是因為我們的鏈表是無法通過當前節點找到前面的節點，只能找到下一個節點，不能和數組那么直接通過下標這樣進行比較。

不過我們發現回文結構的話，我們從中間位置開始，往兩邊走，其都是一樣的，那么我們上面有道題不就是尋找鏈表的中間節點嗎，但是我們該如何從中間節點往前訪問呢？只能說中間節點是頭節點才可以進行遍歷了呀。哎，我們上上道題就是將鏈表進行反轉，那么我們可以在中間節點這個位置，將后面的部分進行反轉，然后再和前面的節點進行比較，不就剛剛好嗎。

代碼如下：

?

?