?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???? ?? ??
??個人主頁 ：阿然成長日記 ??點擊可跳轉
?? 個人專欄： ??數據結構與算法??C語言進階
?? 不能則學，不知則問，恥于問人，決無長進
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

876.鏈表的中間節(jié)點

題目要求:

輸入：head = [1,2,3,4,5]
輸出：[3,4,5]
解釋：鏈表只有一個中間結點，值為 3 。

示例 2：

輸入：head = [1,2,3,4,5,6]
輸出：[4,5,6]
解釋：該鏈表有兩個中間結點，值分別為 3 和 4，返回第二個結點。

思路：
1.定義快指針和慢指針
2.快指針一次走兩步，慢指針一次走一步，
3.快指針走到鏈表最后時，快指針所走的距離正好是慢指針的二倍。

代碼實現：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* low = head;
    struct ListNode* fast = head;

    while(fast && fast->next)
    {
        low = low->next;
        fast = fast->next->next;
    }
    return low;
}

203.移除鏈表元素

題目要求：

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6 輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1 輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7 輸出：[]

思路：
1.如果第一個節(jié)點就是要刪除的。進行頭刪
2.如果head一開始就是空，或者，進行N次頭刪之后，為空。就返回head
3.中間的節(jié)點正常刪除。尾刪與之一樣。

代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-624301.html

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val)
{  	   
        while(head && head->val == val) 
        head = head->next;   //排除第一個節(jié)點就相等的情況
        
        if(!head) //如果刪除第一個，判斷是否就空了
        return head; 

        struct ListNode* slow = head;     //定義快慢指針，也要寫在上一步之后
        struct  ListNode* fast = head->next;

        while(fast) {
            if(fast->val==val) {        //遇到相等就刪除
                slow->next = fast->next;
                fast = slow->next;
            }  else {                   //否則快慢指針依次后移
                slow = slow->next;
                fast = fast->next;
            }
        }
        return head;
    
}

?？皖}—鏈表中倒數第k個結點

題目要求：
輸入一個鏈表，輸出該鏈表中倒數第k個結點。
示例1

輸入： 1,{1,2,3,4,5}
返回值： {5}

思路分析：

注意點：考慮鏈表為空的情況，K的值大于鏈表的長度。

代碼：.

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {

    // write code here

    struct ListNode* fast = pListHead;

    struct ListNode* low = pListHead;



    int i = k-1;

//判斷是否為空，或這k有問題

    if(pListHead==NULL||k<=0)

        return NULL;



    while(i--)

    {

        if(fast->next==NULL)

        {

            return NULL;

        }

        fast = fast->next;

    }

//兩個指針開始同時移動，到最后low表示倒數k的節(jié)點    

    while(fast->next)

    {

        low = low->next;

        fast = fast->next;

    }

    return low;

}

答案正確！
注意：在測試樣例中我發(fā)現個問題。

倒數第五個不應該是1嗎？
原因是，fast后移k-1個，此時fast指針已經指向最后一個元素（fast->next==NULL),所以，根本就沒有進行while循環(huán)，兩個指針同步移動中去。又因為我們最開始給 low= =plisthead，所以，此時返回的是整個鏈表。

反轉鏈表

頭插法：
思路：

從頭開始取鏈表的每一個節(jié)點插入到newnode之前

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newnode = NULL;
    //頭插
    while(cur)
    {
        //定義一個之指針用來保存下一個節(jié)點
        struct ListNode* tmp = cur->next;
        cur->next = newnode;//頭插
        newnode = cur;//將newnode指針前移

        cur = tmp;
    }
    return newnode;
}

cm11-鏈表分割

描述
現有一鏈表的頭指針 ListNode* pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。
思路：

代碼：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* ghead,* gtail,* lhead,* ltail;

        lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
        ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        //遍歷鏈表，大于等于x的放ghead鏈表中，小于x的放lhead鏈表
        while(cur)
        {
            if(cur->val >= x)
            {
                gtail->next = cur;//尾插
                gtail = gtail->next;//移向下一位
            }
            else 
            {
                ltail->next = cur;//尾插
                ltail = ltail->next;
               
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        gtail->next = NULL;
        struct ListNode* head = lhead->next;
        free(lhead);
        free(ghead);
        return head;
    }
};

到了這里，關于【數據結構】“單鏈表”的練習題的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！