??孜孜不倦：孜孜：勤勉，不懈怠。指工作或學習勤奮不知疲倦。💓💓💓
目錄
說在前面
題目一：返回倒數第k個節點
題目二：鏈表的回文結構
題目三：相交鏈表
SUMUP結尾
說在前面
?dear朋友們大家好！💖💖💖數據結構的學習離不開刷題，在對鏈表的相關OJ進行練習后又更新復雜度的OJ，這并不意味這鏈表的題目就結束了，我們今天就繼續聯系鏈表相關的OJ練習。當今天我們的題目除了LeetCode，還來自NowCoder。
?👇👇👇
友友們！🎉🎉🎉點擊這里進入力扣leetcode學習🎉🎉🎉
?以下是leetcode題庫界面：
?
?👇👇👇
🎉🎉🎉點擊這里進入牛客網NowCoder刷題學習🎉🎉🎉
?以下是NowCoder題庫界面：
??
?
??
題目一：返回倒數第k個節點
題目鏈接：面試題 02.02. 返回倒數第 k 個節點 - 力扣（LeetCode）
題目描述：
?
題目分析：
?思路1：將創建一個數組temp，將鏈表中節點的地址存入數組temp，再返回數組中下標為n-k的地址所指向的數據。
舉例：1->2->3->4->5->6? 和 k = 3
?
代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
#define numsSize 100
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;ListNode* temp[numsSize];//創建臨時數組int i = 0;while (pcur != NULL)//將鏈表節點地址存入數組temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒數第k個節點的數據
}不過，假設鏈表很長，此時空間復雜度就會比較高，所以用numsSize固定長度顯然不是好的辦法，應該用動態內存分配的辦法來初始化temp
代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;int length = 0;while (pcur != NULL)//遍歷數組，得到節點的個數{length++;pcur = pcur->next;}//動態創建二級指針變量tempListNode** temp = (ListNode**)malloc(length * sizeof(ListNode*));pcur = head;int i = 0;while (pcur != NULL)//將鏈表節點地址存入temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒數第k個節點的數據
}不過顯然空間復雜度為O(N)，不是一個非常好的辦法。如果給出前提條件：空間復雜度為O(1)，這個方法就不行了。
?思路2：將創快慢指針法：定義快慢指針fast、slow，先讓fast走k步，再讓slow和fast同時走，這樣當fast走完slow剛好指向倒數第k個節點。
舉例：1->2->3->4->5->6? 和 k = 3
?
代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {//定義快慢指針ListNode* slow = head;ListNode* fast = head;while (k--)//讓fast先走k步{fast = fast->next;}//當fast走完，此時slow指向的就是倒數第k個節點while (fast != NULL){fast = fast->next;slow = slow->next;}return slow->val;
}???
題目二：鏈表的回文結構
題目鏈接：鏈表的回文結構_牛客題霸_牛客網 (nowcoder.com)
題目描述：
?
題目分析：
?思路：先找到鏈表的中間節點，再將鏈表的后半部分反轉，比較前半部分和后半部分的元素是否相等。
我們需要用到之前OJ練習1中的兩個函數：
1.鏈表的中間節點：876. 鏈表的中間結點 - 力扣（LeetCode）
2.反轉鏈表：206. 反轉鏈表 - 力扣（LeetCode）
如果忘記了，大家點擊這里復習：LeetCode/NowCoder-鏈表經典算法OJ練習1
代碼如下：
/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://尋找鏈表的中間節點struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反轉鏈表struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* A) {//尋找鏈表的中間節點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;}
};像這種題屬于組合體，比較綜合，同時也告訴我們具有一定功能的代碼在下次使用時可以稍加修改再Ctrl+C/V，可以省去很多麻煩，也比較方便。??
???
題目三：相交鏈表
題目鏈接：160. 相交鏈表 - 力扣（LeetCode）
題目描述：
題目分析：
思路：這題比較復雜，我們需要模塊化思考。同時注意單鏈表相交為"Y"型而不可能為"X"型，因為單鏈表沒有兩個next指針。
1、如何判斷相交？
判斷尾指針，如果尾指針地址相同則相交（注意，不能用尾節點所存儲的值是否相同判斷，因為之前有可能也有節點存儲了和尾節點相同的值）。
2、若相交，如何找出第一個交點？
思路1：A鏈表的節點依次和B鏈表的所有節點比較，A的某個節點和B鏈表的某個節點相等，則這個節點就是交點。
?代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* cur1 = headA;ListNode* cur2 = headB;//讓A、B鏈表都走到尾節點while(cur1->next){cur1 = cur1->next;}while(cur2->next){cur2 = cur2->next;}if(cur1 != cur2)//判斷尾節點是否相等return NULL;cur1 = headA;while(cur1->next)//讓A中每個節點都和B中的所有節點比較{cur2 = headB;while(cur2->next){if(cur1 == cur2)//第一個相等的就是交點return cur2;cur2 = cur2->next;}cur1 = cur1->next;} return cur2;
}這個方法的時間復雜度為O(N^2)。
思路2：分別計算出鏈表A、B的長度，讓長的先走差距的步數，然后再讓兩鏈表同時開始走，第一個相等的就是交點。
代碼如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {ListNode* cur1 = headA, * cur2 = headB;int lenA = 0;int lenB = 0;while (cur1->next)//統計鏈表A的長度{lenA++;cur1 = cur1->next;}while (cur2->next)//統計鏈表B的長度{lenB++;cur2 = cur2->next;}if (cur1 != cur2)//判斷是否有交點return NULL;//假設法，設置長短鏈表ListNode* LongList = headA, * ShortList = headB;if (lenA < lenB){LongList = headB;ShortList = headA;}int gap = abs(lenA - lenB);//兩鏈表節點差值while (gap--)//讓長的先走差值的步數{LongList = LongList->next;}while (LongList != ShortList)//讓兩鏈表一起走，第一個相等的就是交點{LongList = LongList->next;ShortList = ShortList->next;}return LongList;
}這個方法的時間復雜度為O(N)。
對比兩種解法，顯然第二種方法是更好的。?
?
SUMUP結尾
數據結構就像數學題，需要刷題才能對它有感覺。之后還會更新數據結構相關的練習題、面試題，希望大家一起學習，共同進步~
如果大家覺得有幫助，麻煩大家點點贊，如果有錯誤的地方也歡迎大家指出~
)
