什么是网页设计与网站建设,北京网站设计制作过程,中铁建设集团登录,软件网站下载免费目录
前言#xff1a;
1. 删除链表中所有值为key的节点 方法一#xff1a;正常删除#xff0c;头结点另外讨论
方法二:虚拟头结点法 方法三#xff1a;递归
2.反转链表 方法一#xff1a;双指针迭代 方法二#xff1a;递归法解析#xff1a;
3.链表的中间结点 方法…目录
前言
1. 删除链表中所有值为key的节点 方法一正常删除头结点另外讨论
方法二:虚拟头结点法 方法三递归
2.反转链表 方法一双指针迭代 方法二递归法解析
3.链表的中间结点 方法快慢指针法
4. 链表中倒数第k个结点 方法快慢指针方法
5.合并两个有序链表
方法迭代 前言
数据结构想要学的好刷题少不了我们不仅要多刷题还要刷好题为此我开启了一个必做好题锦集的系列每篇大约5题左右。此为第一篇选择题篇该系列会不定期更新敬请期待 1. 删除链表中所有值为key的节点 移除链表元素https://leetcode.cn/problems/remove-linked-list-elements/ 题目描述 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 方法一正常删除头结点另外讨论 public ListNode removeElements(ListNode head, int val) {while(head!nullhead.valval){headhead.next;}if(headnull){return head;}ListNode curhead;while (cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else {curcur.next;}}return head;} 解析 但会漏掉头结点 方法二:虚拟头结点法 public ListNode removeElements(ListNode head, int val) {if(headnull){return head;}ListNode newnodenew ListNode();newnode.nexthead;headnewnode;ListNode curhead;while (cur.next!null){if(cur.next.valval){cur.nextcur.next.next;}else {curcur.next;}}return head.next;} 解析 方法三递归 class Solution {public ListNode removeElements(ListNode head, int val) {if (head null) {return head;}head.next removeElements(head.next, val);return head.val val ? head.next : head;}
} 递归方法之前就是一个压栈的过程递归方法之后就是一个弹栈的过程 2.反转链表 反转链表https://leetcode.cn/problems/reverse-linked-list/
题目描述
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 方法一双指针迭代
public ListNode reverseList(ListNode head) {ListNode prenull;ListNode curhead;while(cur!null){ListNode tmpcur.next;cur.nextpre;precur;curtmp;}return pre;}
解析 我们可以申请两个指针第一个指针叫 pre最初是指向 null 的。第二个指针 cur 指向 head然后不断遍历 cur。每次迭代到 cur都将 cur 的 next 指向 pre然后 pre 和 cur 前进一位。都迭代完了(cur 变成 null 了)pre 就是最后一个节点了。 方法二递归法解析 public ListNode reverseList(ListNode head) {if(headnull || head.nextnull) {return head;}ListNode cur reverseList(head.next);head.next.next head;head.next null;return cur;} 解析 3.链表的中间结点 链表的中间结点https://leetcode.cn/problems/middle-of-the-linked-list/
题目描述
给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 方法快慢指针法 public ListNode middleNode(ListNode head) {if(headnull){return null;}ListNode fasthead;ListNode slowhead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}return slow;} 解析 用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步fast 一次走两步。那么当 fast 到达链表的末尾时slow 必然位于中间。 4. 链表中倒数第k个结点
题目描述
输入一个链表输出该链表中倒数第k个结点。 方法快慢指针方法 public ListNode FindKthToTail(ListNode head,int k) {if(headnull||k0){return null;}ListNode slowhead;ListNode fasthead;while(k-10){fastfast.next;if(fastnull){return null;}k--;}while(fast!nullfast.next!null){fastfast.next;slowslow.next;}return slow;}
解析 首先让快指针先行k-1步然后让快慢指针每次同行一步直到快指针fastnullfast.nextnull慢指针就是倒数第K个节点。 5.合并两个有序链表 合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 方法迭代
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {if(head1null){return head2;}if(head2null){return head1;}ListNode listNode new ListNode();ListNode curlistNode;while(head1!nullhead2!null){if(head1.valhead2.val){cur.nexthead1;head1head1.next;}else{cur.nexthead2;head2head2.next;}curcur.next;}if(head1null){cur.nexthead2;}else{cur.nexthead1;}return listNode.next;} 解析 对head1与head2里的元素进行比较,谁小就与cur连接比如head1的值小就将hea1与cur相连然后向后走一步成为新的head1cur向后走一步成为新的cur,依次类推进行比较 以上为我个人的小分享如有问题欢迎讨论
都看到这了不如关注一下给个免费的赞
