1.鏈表的中間節點
https://leetcode.cn/problems/middle-of-the-linked-list/description/
用快慢指針來解決
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*fast,*slow;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}2.反轉鏈表
https://leetcode.cn/problems/reverse-linked-list/description/
用 三個指針 來解決
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode*n1,*n2,*n3;if(head==NULL)return NULL;n1=NULL;n2=head;n3=n2->next;while(n2){//翻轉n2->next=n1;//移動n1=n2;n2=n3;if(n3)n3=n3->next;}return n1;
}3.將兩個有序鏈表合并為一個新的有序鏈表并返回
21. 合并兩個有序鏈表 - 力扣（LeetCode）
哨兵位解決
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* cur1 = list1, * cur2 = list2;struct ListNode* guard = NULL, * tail = NULL;guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));tail->next = NULL;while (cur1 && cur2){if (cur1->val < cur2->val){tail->next = cur1;tail = tail->next;cur1 = cur1->next;}else{tail->next = cur2;tail = tail->next;cur2 = cur2->next;}}if (cur1){tail->next = cur1;}if (cur2){tail->next = cur2;}struct ListNode* head = guard->next;free(guard);return head;
}4.鏈表分割
現有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。
鏈表分割_牛客題霸_牛客網
哨兵位解決
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode*greaterGuard,*greaterTail,*lessGuard,*lessTail;greaterGuard=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));greaterGuard->next=lessGuard->next=NULL;struct ListNode*cur=pHead;while(cur){if(cur->val<x){lessTail->next=cur;lessTail=lessTail->next;}else{greaterTail->next=cur;greaterTail=greaterTail->next;}cur=cur->next;}lessTail->next=greaterGuard->next;greaterTail->next=NULL;pHead=lessGuard->next;free(lessGuard);free(greaterGuard);return pHead;}
};5.相交鏈表
160. 相交鏈表 - 力扣（LeetCode）
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {struct ListNode* tailA = headA, * tailB = headB;int lenA = 1, lenB = 1;// 處理空鏈表的情況if (headA == NULL || headB == NULL) {return NULL;}while (tailA->next){tailA = tailA->next;lenA++;}while (tailB->next){tailB = tailB->next;lenB++;}// 如果尾節點不同，則鏈表不相交if (tailA != tailB)return NULL;int gap = abs(lenA - lenB);struct ListNode* longlist = headA, * shortlist = headB;// 確定長鏈表和短鏈表if (lenA > lenB){longlist = headA;shortlist = headB;}else{longlist = headB;shortlist = headA;}// 長鏈表先走gap步while (gap--){longlist = longlist->next;}// 同步遍歷找相交節點while (longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}return longlist;
}
