hello，大家好，這里是Dark FlameMaster,今天和大家分享的是有關數(shù)據(jù)結構鏈表的幾道題目，鏈表的中間節(jié)點，反轉鏈表及判斷鏈表是否為回文結構，放在一起講解會印象更加深刻。

一，鏈表的中間節(jié)點

1. 鏈接：鏈表的中間節(jié)點

分析：
?如果想要得到鏈表的中間節(jié)點，最簡單的思路就是從頭結點遍歷整個鏈表，就可以知道鏈表的長度，假設為num個，要求是如果為偶數(shù)個數(shù)，返回第二個節(jié)點。得到個數(shù)后要創(chuàng)建新的節(jié)點，往后走num/2個位置。如果num為奇數(shù)，如5，往后next兩步，如果是偶數(shù)如6,往后next3步，皆滿足要求。
實現(xiàn)：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* ret = head;
    int len = 0;
    int k = 0;
    while(ret)
    {
        ret = ret -> next;
        len++;
    }
    ret = head;
    while(k < len / 2)
    {
        k++;
        ret = ret -> next;
    }
    return ret;
}

此題還有一種雙指針的方法
思路：
?設置快慢指針，快指針一次走兩步，慢指針一次走一步，還是分偶數(shù)和奇數(shù)的情況。
如果是奇數(shù)的話

如果是偶數(shù)的話

要注意觀察fast的最終位置
實現(xiàn)如下

struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* val = NULL;
	struct ListNode* baga = NULL;
	val = head;
	baga = head;
	while (val->next != NULL && val->next->next != NULL)
	{
		val = val->next->next;
		baga = baga->next;
	}
	if (val->next == NULL)
	{
		return baga;
	}
	else
	{
		return baga->next;
	}
}

二，反轉鏈表

鏈接：反轉鏈表

這道題的介紹很簡單，給定一個鏈表head，將鏈表反轉過來。就像這樣。

需要注意的是，這個鏈表的長度有可能為零。
思路：
?解決這道題，不可冒昧更改一個節(jié)點的指向，要記錄后續(xù)節(jié)點，同時還要保留前一個節(jié)點，好讓這個節(jié)點可以指向前一節(jié)點，所以要設置三個結構體指針變量，分別表示要修改的節(jié)點，要修改節(jié)點的前一節(jié)點，該節(jié)點的后邊的節(jié)點。
實現(xiàn)

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1,*n2,*n3;
    n1=NULL;//設置n1為空
    n2=head;//n2為head，首先指向空
    if(n2)
    {
        n3=n2->next;//判斷n2是否為空，若為空則沒有next      
    }
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)//判斷n3是否為空
        {
            n3=n3->next;
        }
    }
    return n1;
}

下邊的動圖可以幫助大家理解

對比代碼看完這些動圖就可以很清晰的理解。

三，鏈表的回文

鏈接：鏈表的回文

設計時間復雜度為O(N),空間復雜度為O(1)的算法

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數(shù)，它定量描述了該算法的運行時間。一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復雜度。

?空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。
?上邊已經(jīng)說了鏈表的長度有限制，空間復雜度為O（1）無疑，只要寫出的代碼中不使用兩層以上循環(huán)遍歷，用有限的多個循環(huán)，時間復雜度都為O(1)
判斷是否為回文結構
如用例中的1-2-2-1，從中間分割后兩邊對稱。
再如
1-2-3-2-1，仍然為回文結構。

如何判斷是否為回文結構呢？好像很難，因為不是雙向鏈表，我們比較的時候找不到尾的前一個，如果硬要一個一個判斷的話，時間復雜度一定不符合要求。

如果使用上邊的兩個題目的思路
?上邊的找中間節(jié)點，剛好為后一個中間節(jié)點，找到中間節(jié)點后，記錄中間節(jié)點后，將中間結點之后的鏈表反轉，反轉后就可以進行比較了。這也是這三道題放在一起的原因。直接cv，將函數(shù)復制過來，判斷函數(shù)內(nèi)容十分簡單，大家可以對照觀察。
思路已經(jīng)十分清楚了
實現(xiàn)如下：

class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* val = NULL;
	struct ListNode* baga = NULL;
	val = head;
	baga = head;
	while (val->next != NULL && val->next->next != NULL)
	{
		val = val->next->next;
		baga = baga->next;
	}
	if (val->next == NULL)
	{
		return baga;
	}
	else
	{
		return baga->next;
	}
}
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    
    if(n2)
    {
        n3=n2->next;
        
    }
        while(n2)
         {
             n2->next=n1;
            n1=n2;
            n2=n3;
             if(n3)//判斷n3是否為空
              n3=n3->next;
         }
    return n1;
}

    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode*mid=middleNode(A);
        struct ListNode* rmid =reverseList(mid);
        while(rmid&&A)
        {
            if(rmid->val!=A->val)
            {
                return false;
            }
            rmid=rmid->next;
        A=A->next;
        }
        return true;

    }
};

鄙人才疏學淺，如果有更好的方法歡迎評論區(qū)留言。
?這三道題講到這里就結束啦，如果有幫助的話希望大家三連支持哇文章來源地址http://www.zghlxwxcb.cn/news/detail-715779.html

到了這里，關于詳解鏈表oJ＜反轉鏈表，鏈表的中間節(jié)點及鏈表的回文＞的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！