a做爰视频免费网站,苏州网站制作排名优化,苏州网络推广公司服务平台,网页设计导航条怎么做1.反转链表
1.1反转链表 如果我们想要反转链表#xff0c;那应该有head的next指针指向空#xff0c;其余结点的next指针反过来#xff0c;指向它的上一个结点#xff0c;那我们在执行该操作的时候就需要定义变量cur(current)表示我们当前遍历到的结点#xff0c;变量pre(…1.反转链表
1.1反转链表 如果我们想要反转链表那应该有head的next指针指向空其余结点的next指针反过来指向它的上一个结点那我们在执行该操作的时候就需要定义变量cur(current)表示我们当前遍历到的结点变量pre(previous)表示上一个结点对于第一个结点来说它的上一个结点为空我们需要把当前的next指针指向上一个结点但两个变量够吗当我们修改当前结点的next指针时它的下一个结点就丢失了所以在修改之前还需要再定义一个变量nxt(next)记录cur的下一个结点之后我们就可以把cur的next指针指向preprecurcurnxt如此循环当反转结束后pre指向反转这一段的末尾cur指向反转这一段末尾的下一个结点所以反转结束时cur指向NULL如图所示 ListNode* reverseList(ListNode* head){ListNode* nxt;ListNode* preNULL;ListNode* curhead;while(cur){nxtcur-next;cur-nextpre;precur;curnxt;}return pre;} 1.2反转链表|| 做这道题我们要用到上一道题的性质当反转结束后pre指向反转这一段的末尾cur指向反转这一段末尾的下一个结点。所以当翻转结束后cur指向5pre指向4所以我们要把2指向cur1指向pre这样就组成了14325我们需要记录反转这一段的上一个结点p所以就是把p的next指向curp指向pre但是当left等于1时是没有p的所以此时我们要建立一个虚拟头结点代码如下
ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummyheadnew ListNode(0,head);ListNode* pdummyhead;for (int i 0; i left - 1; i)p p-next;ListNode *pre NULL, *cur p-next;for (int i 0; i right - left 1; i) {ListNode *nxt cur-next;cur-next pre; pre cur;cur nxt;}p-next-next cur;p-next pre;return dummyhead-next;}
1.3K个一组翻转链表 这个要求我们k个结点一组进行翻转所以我们要先求出来链表的长度如果大于等于k时我们要判断剩余结点的个数小于k是无法翻转的翻转的过程和上一题是一样的需要注意的是我们额外要在翻转之后把p更新成下一段要翻转的链表的上一个结点但是由于最后我们修改了p的next指针所以我们需要在修改之前额外创建一个临时变量nxtp-next翻转结束后令pnxt开始下一段循环不断循环最后返回dummyhead-next代码如下 ListNode* reverseKGroup(ListNode* head, int k) {ListNode* head1head;int len0;while(head1){len;head1head1-next;}ListNode* dummyheadnew ListNode(0,head);ListNode* pdummyhead;ListNode *pre NULL, *cur p-next;for (; lenk;len-k ) {for(int i0;ik;i){ListNode *nxt cur-next;cur-next pre; pre cur;cur nxt;}ListNode* nxtp-next;p-next-next cur;p-next pre;pnxt;
}return dummyhead-next;}
2.链表删除 我们要想删除链表的某个结点需要利用上一个结点的next指针指向删除结点的下一个结点
2.1删除链表中的节点 之前我们在基础数据结构讲过如何删除一个结点但这个它不给我头结点我怎么删除啊这题就很秒它说node不是链表的最后一个结点也就是说我们可以把node结点的下一个结点的值复制过来然后删除下一个结点这可太妙了
void deleteNode(ListNode* node) {node-valnode-next-val;node-nextnode-next-next;
}
2.2 删除链表的倒数第N个结点 第一种做法就是遍历求出链表长度这样我们就知道要删除的倒数第N个结点是正数的第几个了我们再遍历到这个结点的上一个结点执行删除操作同时因为n可能等于链表长度所以我们需要建立虚拟头结点这样就OK了。 第二种做法是快慢指针我们需要找到倒数第N1个结点初始化右指针指向虚拟头结点先让右指针走N步然后初始化左指针指向虚拟头结点左右指针一起向右移动这样两个指针的距离始终为N当右指针走向倒数第一个结点左指针就恰好走到了倒数第N1个结点这时候就可以执行删除操作了
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyheadnew ListNode(0);dummyhead-nexthead;ListNode* slowdummyhead;ListNode* fastdummyhead;while(n--fast!NULL){fastfast-next;}while(fast-next!NULL){slowslow-next;fastfast-next;}slow-nextslow-next-next;return dummyhead-next;}
2.3删除排序链表中的重复元素 这个题还是比较简单的首先并不需要虚拟头结点因为就算头结点的值和下一个结点的值相等也会保留头结点我们只需要遍历链表如果cur的下一个结点的val值和cur的val值相等我们就删除cur的下一个结点需要注意的是循环条件是cur-next当cur遍历到最后一个结点时cur的下一个结点就不存在是NULL此时应该退出循环如果是cur则会继续进入循环造成NULL指针的解引用会报错 ListNode* deleteDuplicates(ListNode* head) {if(headNULL)return NULL;ListNode* curhead;while(cur-next){if(cur-next-valcur-val){cur-nextcur-next-next;}else{curcur-next;}}return head;} 2.4 删除排序链表中的重复元素|| 首先这个题需要建立虚拟头结点因为如果开头就有几个重复的结点那么头结点会被删除所以我们先创建一个虚拟头结点然后初始化cur指针指向虚拟头结点然后遍历链表每次遍历时先取出cur的next的值val如果cur的next的next的值和val相等再进入循环判断cur的next的值是否等于val相等就删除否则移动到下一个结点最后返回头结点 ListNode* deleteDuplicates(ListNode* head) {ListNode* dummyheadnew ListNode(0);dummyhead-nexthead;ListNode* curdummyhead;while(cur-nextcur-next-next){int valcur-next-val;if(cur-next-next-valval){while(cur-nextcur-next-valval){cur-nextcur-next-next;}}else{curcur-next;}}return dummyhead-next;}
