网站开发技术网站模板,百度指数搜索榜,wordpress 本地 搭建网站,电脑网页版微信一、分割链表
题目介绍#xff1a;
思路#xff1a;创建两个链表#xff0c;ghead尾插大于x的节点#xff0c;lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面#xff0c;将大小链表链接。 我们需要在创建两个链表指针#xff0c;指向两个链表的头节点
思路创建两个链表ghead尾插大于x的节点lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面将大小链表链接。 我们需要在创建两个链表指针指向两个链表的头节点用这两个指针标记lhead和ghead的尾结点方便与尾插。
注极端边界场景所有值都小于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){ListNode* gtail, * ghead, * ltail, * lhead;gtail ghead (struct ListNode*)malloc(sizeof(struct ListNode));ltail lhead (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur pHead;while (cur){if (cur-val x){ltail-next cur;ltail ltail-next;}else{gtail-next cur;gtail gtail-next;}cur cur-next;}ltail-next ghead-next;gtail-next NULL;struct ListNode* newhead lhead-next;free(lhead);free(ghead);return newhead;}
}; 二、回文链表
题目介绍 思路先找到中间节点可以利用快慢指针找到中间节点然后将中间节点后面的节点翻转在和中间节点前面的链表依次比较如果全部相同则是回文链表否则不是。 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falst head;slow head;while (falst falst-next){slow slow-next;falst falst-next-next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur head;struct ListNode* newhead NULL;while (cur){struct ListNode* next cur-next;//头插cur-next newhead;newhead cur;cur next;}return newhead;
}class PalindromeList
{
public:bool chkPalindrome(ListNode* head){//找到中间节点将中间节点后面的链表翻转有第一个和中间节点比较并依次后移若全部相同则为回文链表反之不是。struct ListNode* mid middleNode(head);struct ListNode* rmid reverseList(mid);while (rmid mid){if (rmid-val ! head-val){return false;}head head-next;rmid rmid-next;}return true;}};
三、找公共点
题目介绍 思路先遍历两个链表计算出两个链表的长度让后计算出两个链表的长度差k将长的链表先往前走k步然后将两个链表指针同时后移找到第一个相同的节点就是相交节点。
注需要考虑到空链表给链表判空若空headA和headB其中一个为空返回NULL。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA headA;struct ListNode* curB headB;int lenA 1;int lenB 1;if(headANULL||headBNULL){return NULL;}while (curA-next){curA curA-next;lenA;}while (curB-next){curB curB-next;lenB;}if (curA ! curB) //没有交点{return false;}int gap abs(lenA - lenB);struct ListNode* falst headA;struct ListNode* slow headB;if (lenA lenB){falst headB;slow headA;}while (gap--){falst falst-next;}while (slow ! falst){slow slow-next;falst falst-next;}return slow;
}
四、判断是否是环形链表
题目介绍 思路还是利用快慢指针当慢指针往前走一步快指针往前走两步在一个环中每次他们的距离就减少一如果有环就一定能追上。如果没追上则没有环。
用快指针遍历。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head)
{struct ListNode *falsthead;struct ListNode *slowhead;while(falstfalst-next){falstfalst-next-next;slowslow-next;if(falstslow){return true;}}return false;
}
五、寻找环形链表的入环节点
题目描述 思路1假设链表带环头节点head与入环节点的距离为L入环节点与相遇点的距离为D环的大小为C如下图 fast从头节点到相遇点L D kC其中k为正整数表示在快慢指针相遇前fast所走圈数 slow从头节点到相遇点L D 又由于fast每次走两步slow每次走一步以上二式可以建立起联系 L D kC 2 * (L D) L kC - D (k - 1) * C C - D 所以可以得出结论一个指针从相遇点开始走一个指针从链表头开始走则这两个指针一定会在入环节点处相遇。 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fasthead, *slowhead;while(fast fast-next){fastfast-next-next;slow slow-next;if(fast slow){//找相遇点meetNodestruct ListNode* meetNode fast;//相遇点可能就是入环节点if(meetNode head)return head;//meetNode和head开始每次走一步直到相遇while(head meetNode){meetNode meetNode-next;head head-next;//当相遇时即为入环节点if(meetNode head)return meetNode;}}}return NULL;
}
思路2我们可以在相遇点将链表断开找到如节点就相当于找到两个链表的交点。
找两个链表的交点我们可以参考题目三
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *curAheadA;struct ListNode *curBheadB;int lenA1;int lenB1;while(curA-next){curAcurA-next;lenA;}while(curB-next){curBcurB-next;lenB;}if(curA!curB) //没有交点{return false;}int gapabs(lenA-lenB);struct ListNode *falstheadA;struct ListNode *slowheadB;if(lenAlenB){falstheadB;slowheadA;}while(gap--){falstfalst-next;}while(slow!falst){slowslow-next;falstfalst-next;}return slow;
}
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *fasthead;struct ListNode *slowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast) //相遇了{struct ListNode *meetslow; //将环断开struct ListNode *newheadmeet-next;meet-nextNULL;return getIntersectionNode(head,newhead); //找两个链表的交点}}return NULL;
}
