目錄

?編輯題一：鏈表分割

思路一：

題二：相交鏈表

思路一：

題三：環形鏈表

?思路一：

題四：鏈表的回文結構

思路一：

鏈表反轉：

查找中間節點：

本人實力有限可能對一些地方解釋的不夠清晰，可以自己嘗試讀代碼，望海涵！

---

題一：鏈表分割

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

思路一：

1.分別創建一個記錄小于x的“小”結構體，和記錄大于等于x的“大”結構體，

2.然后malloc函數動態開辟一個結構體大小的空間，這時head和tail都指向同一位置，將phead->val與x比較，小于想，放入less中，大于等于x放入great中，

3.當phead為NULL時，將兩個“大”“小”結構體鏈接起來，記錄lesshead節點，然后free釋放開辟的動態內存空間，返回記錄lesshead的地址。

    ListNode* partition(ListNode* phead, int x) {struct ListNode* head = phead ; struct ListNode* lesshead ;struct ListNode* greathead ; struct ListNode* lesstail ; struct ListNode* greattail ; //動態開辟空間lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));while(head){//小于x的尾插到lessTailif(head->val < x){lesstail->next  = head;lesstail = lesstail->next;            }//大于等于x的尾插到greaterTailelse{greattail->next  = head;greattail = greattail->next; }//下一個位置head = head->next;  }//小的接上大的lesstail->next = greathead->next;greattail->next = NULL;//新頭節點struct ListNode* Phead = lesshead->next;//銷毀free(lesshead);free(greathead);return Phead;}

題二：相交鏈表

給你兩個單鏈表的頭節點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回?null?。

圖示兩個鏈表在節點?c1?開始相交：

題目數據?保證?整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須?保持其原始結構?。

思路一：

1.先分別將A和B遍歷一遍，計算出長度len
2.計算長度差Slen，讓長的先指向Slen個next位置
3.此時再同時遍歷，直到A和B的地址相同，
4.返回的就是第一個交點

?

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode* curA = headA,*curB = headB;int len1 = 1,len2 = 1; //計算鏈表長度while(curA){curA = curA->next;len1++;}while(curB){curB = curB->next;len2++;}//如果此時遍歷結束地址不相等，說明沒有相交點if(curA != curB){return NULL;}//abs是計算差值絕對值函數int Slen = abs(len1 - len2);//二次遍歷的長短鏈表struct ListNode* longlist = headA,*shortlist = headB;if(len1 <  len2){longlist = headB;shortlist = headA;}//讓longlist和shortlist的長度相同while(Slen--){longlist = longlist->next;}//找到第一個交點while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}//輸出交點地址return longlist;
}

題三：環形鏈表

給你一個鏈表的頭節點?head?，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回?true?。 否則，返回?false?。

示例 1：

?思路一：

快慢指針思路:
1.創建快慢指針fast和slow；
2.開始位置相同，slow每次指向下一個地址， fast每次指向下下個地址；
3.循環判斷，直到slow=fast地址相同；

4，相同則說明鏈表存在環；
反之，fast或fast->next尾NULL則不存在環。

bool hasCycle(struct ListNode *head)
{struct ListNode* slow = head;struct ListNode* fast = head;//fast或fast->next尾NULL則不存在環while(fast && fast->next){//slow每次指向下一個地址， fast每次指向下下個地址slow = slow->next;fast = fast->next->next;//相同則說明鏈表存在環if(slow == fast){return true;}}return false;
}

題四：鏈表的回文結構

思路一：

如下：兩種方法，得到的節點去循環判斷，如果newnode或者head一個為NULL，則說明是回文結構，如果在循環中結束·，則不是回文結構。

鏈表反轉：

三個變量n1=NULL,n2=head,n3,如果n2不為NULL，則n3=n2->next，循環如果n2為NULL，就停下來，當n3為空時n3就不進行變化，最后n1會停在最后一個位置，這個時候逆置完成。

查找中間節點：

分別定義快慢兩個指針，快指針一次前進兩個地址，慢指針一次前進一個地址，當奇數時快指針的next為NULL時，當鏈表為偶數時判斷條件為地址為NULL，停下來，此時慢指針就在鏈表中間節點上。

//將鏈表反轉
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->next;}return n1;
}
//得到鏈表中間節點
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;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* head) {struct ListNode* mid = middleNode(head);struct ListNode* newnode = reverseList(mid);//一個為空自己退出while(newnode && head){//不相同，則不是回文結構if(newnode->val != head->val){return false;}newnode = newnode->next;head = head->next; }return true;}
};

本人實力有限可能對一些地方解釋的不夠清晰，可以自己嘗試讀代碼，望海涵！