鏈表OJ題（一）

前面我們已經認識到了單鏈表，在具體的面試題中是怎么考察的呢？看完這些OJ講解，或許你對鏈表會有新的認識！

目錄

一、洗掉鏈表中值為val的結點

二、反轉鏈表

三、尋找鏈表的中間結點

四、回傳鏈表中倒數第k個結點

一、洗掉鏈表中值為val的結點

思路：我們可以遍歷一遍鏈表，遇到val的結點我們就可以將其洗掉

注意特殊情況：1、當鏈表為空時

2、頭結點就是要洗掉的結點

我們可以定義兩個指標變數prev（previous）和cur（current），prev記錄上一個結點的地址，cur表示當前位置地址

動圖演示：

代碼如下：

struct ListNode
 {
     int val;
     struct ListNode *next;
 };
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev=NULL,*cur=head;
    while(cur)
    {
        if(cur->val==val)
        {//prev可能為空指標解參考
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
            prev->next=cur->next;
            free(cur);
            cur=prev->next;
            }
        }
        else
        {
        prev=cur;
        cur=cur->next;
        }
    }

洗掉程序中應該記住，先指向再洗掉，因為先洗掉之后你就不能找到cur的下一個位置了

特殊情況下當val就是頭結點，prev->next這里就是空指標的解參考，所以我們要進行頭刪處理

記錄head的下一個結點的位置再進行洗掉

二、反轉鏈表

思路一：我們可以把鏈接關系反向，就相當于把鏈表給反轉了

為了方便操作，我們定義三個指標變數，分別是n1 n2 n3

n1：將要反轉結點的前一個結點

n2：將要反轉的結點

n3：將要反轉結點的下一個結點

動圖演示中間迭代程序：

結束條件分析可以知道，當圖中n2=NULL時就停止了

代碼如下：

struct ListNode 
{
	int val;
	struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{
    
    if(head==NULL)//因為后面head需要解參考所以必須要考慮鏈表為NULL的情況
    {
        return NULL;
    }
 
    ListNode*n1 = NULL;
    ListNode*n2 = head;
    ListNode*n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        //n2為NULL為回圈結束條件，需保證n3不為NULL時，再迭代n3
        if(n3)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

特殊情況：當傳入空鏈表時，我們就不需要反轉，直接回傳NULL

當結束時，n3會提前到NULL，此時需要特判一下，預防野指標

思路二：我們可以利用頭插法，創建一個新的結點newnode，把原來結點拿下來頭插，最后回傳newnode地址

動圖演示：

迭代結束的條件就是當cur走到NULL時就回圈停止了

代碼入下：

struct ListNode {
	int val;
	struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* cur = head;//記錄當前待頭插的結點
	struct ListNode* newnode = NULL;//新鏈表初始時為空
	while (cur)//鏈表中結點頭插完畢時停止回圈
	{
		struct ListNode* next = cur->next;//記錄下一個待頭插的結點
		cur->next = newnode;//將結點頭插至新鏈表
		newnode = cur;//新鏈表頭指標后移
		cur = next;//指向下一個待頭插的結點
	}
	return newnode;//回傳反轉后的頭指標
}

三、尋找鏈表的中間結點

我們很容易想到，先遍歷一遍找到結點總數，在遍歷一遍找到結點的一半，這樣時間復雜度就較高為 O(n^2),我們能不能將其優化到O(n)呢？

思路：用快慢指標fast（走兩步）和slow（走一步），當fast=NULL時，slow就是中間結點，但我們還要考慮奇偶結點問題，仔細畫圖，當為偶數個結點時，結束條件就是fast的下個結點為NULL

影片演示：

奇數結點情況

偶數結點情況：

代碼如下：

struct ListNode {
	int val;
	struct ListNode *next;
};

struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast&&fast->next)//遍歷繼續的條件
	{
		slow = slow->next;//慢指標一次走一步
		fast = fast->next->next;//快指標一次走兩步
	}
	return slow;//回傳慢指標
}

四、回傳鏈表中倒數第k個結點

思路：也是使用快慢指標，這里稍有不同點

1、fast先走k步

2、然后fast和slow一起走，直到fast走到NULL，那么slow就是倒數第k個結點

動圖演示：

代碼如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{struct ListNode*fast,*slow;
 fast=slow=pListHead;
 //fast先走k步
 while(k--)
 {
     
     if(fast==NULL)//特判一下，當K大于鏈表長度時
     return NULL;
     fast=fast->next;
     
 }
 while(fast)
 {
     fast=fast->next;
     slow=slow->next;
 }
    return slow;
}

需要注意特判一下的就是，當k大于鏈表長度時或者鏈表就是空鏈表時，我們的fast會越界訪問，所以這里當fast=NULL時，我們直接return NULL;即可

謝謝各位博友的觀看！！