题目一 分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。
我们来看图
还是使用我们上期用过的哨兵位头节点容易做一点 刷爆leetcode第一期-CSDN博客
1.分别开辟两个哨兵位头节点lguard，Gguard，以及他们的尾节点ltail，Gtail，再定义一个cur指针指向原链表头指针，方便向后走
2.比较比x小的尾插到lguard链表中，反之则尾插到Gguard链表中，cur，ltail，Gtail，分别向后走
3.最后将Gguard尾插到lguard
4.将lguard和Gguard释放（不可忽略）
看代码：
struct ListNode { int val; struct ListNode* next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* partition(ListNode* pHead, int x) { struct ListNode* lguard, * ltail, * Gguard, * Gtail; lguard = ltail = (struct ListNode*)malloc(sizeof(struct ListNode)); Gguard = Gtail = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = pHead; ltail->next = NULL; Gtail->next = NULL; while (cur) { if (cur->val < x) { ltail->next = cur; ltail = ltail->next; } else { Gtail->next = cur; Gtail = Gtail->next; } cur = cur->next; } ltail->next = Gguard->next; Gtail->next = NULL; pHead = lguard->next; free(lguard); free(Gguard); return pHead; } };
注意一定要把哨兵位头节点释放
题目二 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
看图
这道题就要用到我们上一期做题的思路刷爆leetcode第一期-CSDN博客
1.找到中间节点
2.从中间节点开始对后半段逆置
3.前半段和后半段比较就可以了
看代码：
struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ //找到中间节点 struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = NULL, * fast = NULL; slow = fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } //逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while (cur) { struct ListNode* next = cur->next;//保存下一个位置 cur->next = newhead;//头插到newhead newhead = cur;//更新头节点 cur = next; } return newhead; } class PalindromeList { public: bool chkPalindrome(ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* rhead = reverseList(mid); while (head && rhead) { if (head->val != rhead->val) { return false; } else { head = head->next; rhead = rhead->next; } } return true; } };
题目三 双链表相交节点
输入两个链表，找出它们的第一个公共节点。
1.分别求俩个链表的长度
2.长的先走差距步
3.同时走，第一个地址相同就是交点
看代码：
/** * 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; int lenB = 1; //计算链表A的长度 while (tailA->next) { tailA = tailA->next; ++lenA; } while (tailB->next)//B的长度 { tailB = tailB->next; ++lenB; } int gap = abs(lenA - lenB);//长度差的绝对值 struct ListNode* longlist = headA, * shortlist = headB; if (lenA < lenB)//判断谁长谁短 { longlist = headB; shortlist = headA; } //长的先走差距步 while (gap--) { longlist = longlist->next; } //同时走 while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return longlist; }
