目錄

1. 題目1：返回倒數第k個節點

1.1 題目鏈接及描述

1.2 解題思路

1.3 程序

2. 題目2：鏈表的回文結構

2.1 題目鏈接及描述

2.2 解題思路

2.3 程序

---

1. 題目1：返回倒數第k個節點

1.1 題目鏈接及描述

題目鏈接：

面試題 02.02. 返回倒數第 k 個節點 - 力扣（LeetCode）

題目描述：

實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該節點的值。

（該題目已保證給定k保證有效）

1.2 解題思路

思路1：計數轉換為正數

遍歷單鏈表計數，假設計得鏈表結點數為n，倒數第k個元素即正數第n-k個元素，再遍歷返回第n-k個結點的值即可；

時間復雜度O(N)（但遍歷鏈表兩遍），空間復雜度O(1)；

思路2：存儲到數組中再下標訪問正數元素

新創建一個數組，遍歷單鏈表，依次將鏈表的結點值記錄到數組中，假設計得鏈表結點數為n，結點值分別記錄到數組下標0~n-1的位置，返回下標為n-k的數組元素值即可；

時間復雜度O(N)，空間復雜度O(N)；

思路3：快慢指針（本題解法）

創建兩個指針，一個指針指向鏈表第一個結點，稱為慢指針；一個指針指向鏈表第k個結點，稱為快指針；

令兩個指針同時向后遍歷，直至快指針指向空時，此時慢指針即指向倒數第k個結點；

時間復雜度O(N)（只遍歷鏈表一遍），空間復雜度O(1)；

1.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* fast=head,*slow=head;// 令fast先走k步while(k--){fast=fast->next;}// 快慢同時走while(fast){slow=slow->next;fast=fast->next;}return slow->val;
}

2. 題目2：鏈表的回文結構

2.1 題目鏈接及描述

題目鏈接：鏈表的回文結構_牛客題霸_牛客網

題目描述：

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。
給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

2.2 解題思路

思路1：

存儲到數組，再創建兩個計數變量分別從前向后和從后向前進行遍歷來進行回文判斷。

時間復雜度：O(N)，空間復雜度：O(N)（不符合要求）；

思路2：（本題解法）

第一步：定位鏈表的中間結點；

第二步：從中間結點開始，將鏈表的后半段逆置；

第三步：創建兩個指針，一個指向鏈表第一個結點，一個指向鏈表的中間結點，兩個同時向后走；

對于偶數個結點的鏈表，直至其中一個指針指向空即可對應匹配結束：

對于奇數個結點的鏈表，由于逆置的后半段鏈表并不影響原鏈表中間結點的的本來指向，未逆置的前半段鏈表的最后一個結點的指向其實還是指向原鏈表的結點，最終比較也是奇數個結點鏈表的中間結點的自我比較，匹配結束標志仍是任意一個指針指向空：

2.3 程序

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
using ListNode = struct ListNode;
class PalindromeList {public:// 查找中間結點struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;}return slow;}// 逆置鏈表struct ListNode* reverseList(struct ListNode* head) {// 判空if (head == NULL) {return head;}// 創建三個指針ListNode* n1 = NULL;ListNode* n2 = head;ListNode* n3 = n2->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}// 判斷回文bool chkPalindrome(ListNode* A) {// 查找中間鏈表ListNode* midNode=middleNode(A);// 逆置后半段鏈表ListNode* remidNode=reverseList(midNode);while(remidNode && A){if(remidNode->val != A->val){return false;}remidNode=remidNode->next;A=A->next;}return true;}
};

注：關于查找單鏈表中間結點、逆置鏈表的實現，在OJ相關文章有詳解，文章鏈接如下：

【數據結構】_鏈表經典算法OJ（力扣版）-CSDN博客文章瀏覽閱讀1.3k次，點贊33次，收藏21次。4、考慮特殊情況及相應處理：（1）原鏈表為空：即head=NULL，導致curNode=NULL，不會進入第一個while循環，但在newTail->next=NULL 時會導致空指針解引用操作，出現錯誤。故需對newTail是否為空進行單獨討論處理。（2）新鏈表為空：即原鏈表所有結點數據域的值都等于val，導致newTail->next=NULL 時會導致空指針解引用操作，出現錯誤。同（1）：需對newTail是否為空進行單獨討論處理。處理邏輯為：https://blog.csdn.net/m0_63299495/article/details/145355272https://blog.csdn.net/m0_63299495/article/details/145355272