从网络全角度考量_写出建设一个大型电影网站规划方案,金乡县住房和城乡建设局网站,网络广告的优势有哪些,淄博市住房和城乡建设局官方网站目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表
定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* p…
目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表
定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* partition(struct ListNode* head, int x)
{struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;lesshead lesstail (struct ListNode*)malloc(sizeof(struct ListNode));lesstail-next NULL;greaterhead greatertail (struct ListNode*)malloc(sizeof(struct ListNode));greatertail-next NULL;struct ListNode* cur head;while (cur){if (cur-val x){lesstail-next cur;lesstail cur;}else{greatertail-next cur;greatertail cur;}cur cur-next;}lesstail-next greaterhead-next;greatertail-next NULL;struct ListNode* newhead lesshead-next;free(lesshead);free(greaterhead);return newhead;
}剑指 Offer II 027 回文链表
先找到链表中间节点将中间节点以后的节点从原链表截断逆置生成新链表与原链表逐节点的值相比较
//回文结构
bool isPalindrome(struct ListNode* head) {if (head NULL){return false;}//找中间节点struct ListNode* cur head, * slow head, * fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}struct ListNode* mid slow;//将中间节点之后的顺序反转struct ListNode* newhead slow;cur newhead;struct ListNode* prev NULL;while (cur){struct ListNode* next cur-next;cur-next prev;prev cur;cur next;}newhead prev;//遍历两组链表检查是否每位相等struct ListNode* cur2 newhead;struct ListNode* cur1 head;while (cur1 cur2){if (cur1-val ! cur2-val){return false;}cur1 cur1-next;cur2 cur2-next;}return true;
}160 相交链表
根据两链表长度求出长度差k较长的链表先走k步两表再一起走节点地址相同时返回此节点 int ListSize(struct ListNode * head){struct ListNode * curhead;int len0;while(cur){len;curcur-next;}return len;}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1ListSize(headA);int len2ListSize(headB);int kabs(len1-len2);struct ListNode * longlistheadA;struct ListNode * shortlistheadB;if(len1len2){longlistheadB;shortlistheadA;}struct ListNode * cur1longlist, *cur2shortlist;while(k--){cur1cur1-next;}while(cur1 cur2){if(cur1cur2){return cur1;}cur1cur1-next;cur2cur2-next;}return NULL;
}141 环形链表
快慢指针法相遇则为环形链表
//环形链表快慢指针法
bool hasCycle(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){fast fast-next-next;slow slow-next;if (slow fast){return true;}}return false;
}142 环形链表 II
先找到入环点相遇点到入环点的距离等于链头到入环点的距离从链头和相遇点出发相遇点即为入环点 //环形链表 II
//找到入环点再判断环形链表代码块内续写
struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* slow head, * fast head, * meet NULL;while (fast fast-next){//找到快慢指针相遇点fast fast-next-next;slow slow-next;//相遇点到入环点的距离等于链头到入环点的距离if (slow fast){meet slow;while (meet ! head){meet meet-next;head head-next;}return meet;}}return NULL;
}138 复制带随机指针的链表
在原链表每个节点后复制一个节点根据原节点设置复制节点的random 注意不可复制节点的同时处理random因为random指向位置还未完成复制 将处理好的复制节点链接到newhead
//复制带随机指针的链表
struct Node* copyRandomList(struct Node* head) {struct Node* cur head;//在原链表每个节点后复制一个节点while (cur){struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;copy-next cur-next;cur-next copy;cur copy-next;}cur head;struct Node* next NULL;//根据原节点设置复制节点的randomwhile (cur){struct Node* copy cur-next;next copy-next;if (cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur next;}//将处理好的复制节点链接到newheadcur head;struct Node* newtail NULL, * newhead NULL;while (cur){struct Node* copy cur-next;next copy-next;if (newtail NULL){newhead newtail copy;}else{newtail-next copy;newtail copy;}cur-next next;cur next;}return newhead;
}
