新浪微博网站建设,邯郸最近发生的重大新闻,广告软文范例大全100,东莞做网站的联系电话目录一.删除链表中等于给定值的节点二.合并有序链表并返回三.链表的回文结构1.反转单链表2.返回非空链表的中间节点四.输出链表倒数第K个节点五.基于给定值x分割单链表六.返回两个链表的第一个中间节点一.删除链表中等于给定值的节点
我们先来看第一题(题目链接): 因为我们需…
目录一.删除链表中等于给定值的节点二.合并有序链表并返回三.链表的回文结构1.反转单链表2.返回非空链表的中间节点四.输出链表倒数第K个节点五.基于给定值x分割单链表六.返回两个链表的第一个中间节点一.删除链表中等于给定值的节点
我们先来看第一题(题目链接): 因为我们需要从链表中删除满足条件的值所以必须使用两个指针一个用来遍历链表另一个记录上一个节点的位置。接着我们以遍历链表的指针不为空为循环条件编写代码当当前节点的val值不等于给定x值时就向下遍历否则移除当前位置的节点。需要注意的一个特殊情况就是链表第一个节点的值就等于给定的x值时就需要移动头节点。代码如下:
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode*prev NULL,*curhead;while(cur){if(cur-val ! val){prevcur;curcur-next;}else {if(prev NULL){headcur-next;free(cur);curhead;}else{prev-nextcur-next;free(cur);curprev-next;}}}return head;
}二.合并有序链表并返回
我们接着看下一题(题目链接) 这题的思路我们可以新malloc一个链表然后定义两个指针指向链表的头节点然后遍历比较两个给的链表的val数值将较小的插入到新链表中。最后返回即可。代码如下:
truct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode*nextnode (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curnextnode;struct ListNode* headnextnode;if(!list1)return list2;else if(!list2)return list1;else{while(list1list2){if(list1-vallist2-val){cur-nextlist1;curcur-next;list1list1-next;cur-nextNULL;}else{cur-nextlist2;curcur-next;list2list2-next;cur-nextNULL;}}if(list1)cur-nextlist1;if(list2)cur-nextlist2;return head-next;}
} 三.链表的回文结构
1.反转单链表
我们看一下反转链表这一题(题目链接) 这题我们定义三个指针prev用来保存上一个节点的地址初始化为NULLcurr初始化指向链表的头节点用来遍历链表next用来保存遍历中下一个节点即可代码如下大家理解一下:
struct ListNode* reverseList(struct ListNode* head){struct ListNode*prevNULL;struct ListNode*currhead;while(curr){struct ListNode*nextcurr-next;curr-nextprev;prevcurr;currnext;}return prev;
}2.返回非空链表的中间节点
(题目链接) 这题有个妙招------快慢指针我们定义fast slow两个指针都指向头节点不同的是快指针一次走两步而慢指针一次只走一步。考虑到链表是偶数个还是奇数个的问题当快指针或者快指针的下一个节点走到NULL时慢指针就走到了链表的中间节点代码如下:
struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow,*fast;slowfasthead;while(fast fast-next){fastfast-next-next;slowslow-next;}return slow;
}基于上面两题的讲解我们来看下这题(题目链接) 这题我们的思路就是找到链表的中间节点后反转后半段链表后与前半段链表进行比较如果在遍历走到空指针之前全部相同则就是回文结构。 代码如下:
class PalindromeList {public:struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev NULL;struct ListNode* curr head;while (curr) {struct ListNode* next curr-next;curr-next prev;prev curr;curr next;}return prev;}struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow, *fast;slow fast head;while (fast fast-next) {fast fast-next-next;slow slow-next;}return slow;}bool chkPalindrome(ListNode* A) {struct ListNode*mid middleNode(A);struct ListNode* rheadreverseList(mid);while(A rhead){if(A-val ! rhead-val)return false;AA-next;rheadrhead-next;}return true;}
};四.输出链表倒数第K个节点
我们看下题目(题目链接) 这题使用快慢指针的话也是非常简单我们定义快慢指针指向链表头节点然后先让快指针走k步后再让快慢指针同时走等快指针走到空指针时满指针就走到了倒数第K个节点。 代码如下:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slowpListHead;struct ListNode* fastpListHead;while(k--){if(fast NULL)return NULL;fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow;
}五.基于给定值x分割单链表
我们看下一题(题目链接) 这题我们可以新malloc两个节点然后以给定值x将链表分割到两个链表中最后将两个链表串起来即可。 代码如下:
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode*guard1,*guard2,*tail1,*tail2;tail1guard1(ListNode*)malloc(sizeof(ListNode*));tail2guard2(ListNode*)malloc(sizeof(ListNode*));tail1-nexttail2-nextNULL;ListNode* curpHead;while(cur){if(cur-valx){tail1-nextcur;curcur-next;tail1tail1-next;}else {tail2-nextcur;curcur-next;tail2tail2-next;}}tail1-nextguard2-next;tail2-nextNULL;return guard1-next; }
};六.返回两个链表的第一个中间节点
我们先看一下题目(题目链接) 做这题时我们要想清楚如果两个链表有相交的节点那再这节点后两个链表都指向同一个地址
上图这种情况是不存在的 所以我们可以得知两个有相交节点的链表最后的节点的地址是相等的(当然相交节点后都相同只因在单链表中尾节点比较好找) 代码如下:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int len1,len2;len1len21;struct ListNode *tail1headA;struct ListNode *tail2headB;while(tail1){tail1tail1-next;len1;}while(tail2){tail2tail2-next;len2;}if(tail1 !tail2)return NULL;int gapabs(len1-len2);struct ListNode *longheadheadA;struct ListNode *shortheadheadB;if(len2len1){longheadheadB;shortheadheadA;}while(gap--)longheadlonghead-next;while(shorthead ! longhead){shortheadshorthead-next;longheadlonghead-next;}return longhead;
}
