建设工程敎育网网站,星子网易云,公司手机网站,网站中英文切换代码目录 一、移除链表元素思路1#xff1a;思路2#xff1a; 二、反转链表三、链表的中间节点四、链表中倒数第k个节点五、回文结构六、合并两个有序链表 一、移除链表元素
题目#xff1a;
思路1#xff1a;
在原来的链表上进行修改#xff0c;节点的数据是val的删除思路2 二、反转链表三、链表的中间节点四、链表中倒数第k个节点五、回文结构六、合并两个有序链表 一、移除链表元素
题目
思路1
在原来的链表上进行修改节点的数据是val的删除然后前后再连接起来。
需要考虑的因素 1.要删除的节点位置在第一个节点 2.要删除的节点位置在中间任意一个节点 3.要删除的节点位置在最后一个节点
用一个变量cur遍历链表要删除的节点是头节点就是头删是中间的某个节点就把要删除的节点free释放然后连接前后的节点定义另一个变量prev为cur的前一个是最后一个节点就是尾删但是这里的尾删与中间某个节点删除是一样的。
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* curhead;struct ListNode* prevNULL;while(cur){if(cur-valval){if(curhead){headcur-next;free(cur);curhead;}else{prev-nextcur-next;//cur是尾节点next就是空free(cur);curprev-next;}}else{prevcur;curprev-next;}}return head;
}思路2
将不是要移除的元素连接到新的链表
这里我们要定义一个新的头指针newhead还要一个变量cur去遍历原链表找不是要移除的元素再定义一个变量tail使每次插入的新节点链接起来。
注意在最后要把tail的next置空因为尾节点的next必须指向空指针
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* cur head;struct ListNode* newheadNULL;struct ListNode* tail newhead;while(cur){if(cur-valval){curcur-next;}else{if(tailNULL){newheadtailcur;}else{tail-nextcur;tailtail-next;}curcur-next;}}if(tail){tail-nextNULL;}return newhead;
}二、反转链表
题目 采用头插法
定义一个新的头指针newhead指向NULL用一个变量cur遍历原链表再定义一个变量del为cur的下一个节点这样cur循环一次可以到原来链表的下一个节点。头插时让cur的next指向newhead再把newhead移到cur的位置上去直到把原链表的所有节点头插完返回的newhead就是原链表的反转。 struct ListNode* reverseList(struct ListNode* head)
{//头插struct ListNode* newheadNULL;struct ListNode* curhead;while(cur){struct ListNode* delcur-next;cur-nextnewhead;newheadcur;curdel;}return newhead;
}三、链表的中间节点
题目 快慢指针法
定义两个指针变量fast(快指针)和slow(慢指针)快指针一次走两步慢指针一次走一步。当快指针或者快指针的next有一个为空指针时跳出循环返回慢指针就是中间节点。 struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
}四、链表中倒数第k个节点
题目 快慢指针相对距离法
定义两个指针变量fast和slow先让fast走k步如果fast已经为空k还没结束就返回空然后fast和slow一起走速度相同当fast为空时跳出循环此时的slow就是倒数第k个节点。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* slow pListHead;struct ListNode* fast pListHead;while(k)//先走k步{if(fastNULL){return NULL;}fastfast-next;k--;}while(fast!NULL)//相对距离{fastfast-next;slowslow-next;}return slow;
}五、回文结构
题目 这道题其实是前面两个题的综合 采用找中间节点和反转链表然后比较是否回文
先找到中间节点然后在这个中间节点开始反转后面的节点比较从头节点开始到中间节点的个数如果相同就是回文返回true否则返回false。 class PalindromeList {
public:ListNode* find(ListNode* head){ListNode* slowhead;ListNode* fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;}ListNode* reverse(ListNode* head){ListNode* newheadNULL;ListNode* curhead;while(cur){ListNode* delcur-next;cur-nextnewhead;newheadcur;curdel;}return newhead;}bool chkPalindrome(ListNode* head) {ListNode* ridfind(head);ListNode* mridreverse(rid);ListNode* curhead;while(cur!rid){if(cur-val!mrid-val){return false;}curcur-next;mridmrid-next;}return true;}
};六、合并两个有序链表
题目 两个链表的节点从头开始比较取小的尾插到新链表如果有一个链表的节点还没尾插完就直接将这个链表的剩余节点尾插到新链表去。
如果刚开始有某个链表为空就直接返回另一个链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL){return list2;}if(list2NULL){return list1;}struct ListNode* headNULL;struct ListNode* tailNULL;while(list1list2){if(list1-vallist2-val){if(tailNULL){headtaillist1;}else{tail-nextlist1;tailtail-next;}list1list1-next;}else{if(tailNULL){headtaillist2;}else{tail-nextlist2;tailtail-next;}list2list2-next;}}if(list1){tail-nextlist1;}if(list2){tail-nextlist2;}return head;
}感谢观看~
