【数据结构】单链表练习

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;
}