vs 2017c 怎么建设网站,南通小程序制作,有找猎聘网站做简历优化的,最近一周的重大新闻提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言链表1、BM1 反转链表2、BM2 链表内指定区间反转3、BM3 链表中的节点每k个一组翻转4、BM4 合并两个排序的链表5、BM5 合并k个已排序的链表6、BM6 判断链表中是否… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言链表1、BM1 反转链表2、BM2 链表内指定区间反转3、BM3 链表中的节点每k个一组翻转4、BM4 合并两个排序的链表5、BM5 合并k个已排序的链表6、BM6 判断链表中是否有环7、BM7 链表中环的入口结点8、BM8 链表中倒数最后k个结点9、BM9 删除链表的倒数第n个节点10、BM10 两个链表的第一个公共结点11、BM11 链表相加(二)12、BM12 单链表的排序13、BM13 判断一个链表是否为回文结构14、BM14 链表的奇偶重排15、BM15 删除有序链表中重复的元素-I16、BM16 删除有序链表中重复的元素-II 总结 前言
提示
本章节全部基于牛客网的题库中的在线编程面试必刷TOP10101-链表总共十六道题目。 提示以下是本篇文章正文内容下面案例可供参考
链表 1、BM1 反转链表
题目描述 给定一个单链表的头结点长度为n反转该链表后返回新链表的表头。 0≤n≤1000要求空间复杂度O1、时间复杂度O1 代码如下
public class BM1 {/*** param head : 给定一个链表的头节点* return 返回反转链表后的新的头节点*/public ListNode ReverseList(ListNode head) {// base caseif (head null || head.next null) {return head;}// 利用指针(pre记录之前遍历过的节点cur为当前正在操作的节点next保存原始链表顺序ListNode pre null, cur head, next null;while (cur ! null) {next cur.next;cur.next pre;pre cur;cur next;}return pre;}
}总结
其实这道题很经典但是在设置指针的时候很容易出错需要熟练使用指针。确保将一个指针记录之前操作过的链表节点一个指针为正在操作的节点一个指针保存原始链表顺序。 2、BM2 链表内指定区间反转
题目描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转要求时间复杂度 O(N)空间复杂度O(1)。 给出的链表为 1→2→3→4→5→NULL, m2,n4, 返回 1→4→3→2→5→NULL. 代码实现
public class BM2 {/*** param head ListNode类* param m int整型* param n int整型* return ListNode类*/public ListNode reverseBetween(ListNode head, int m, int n) {// write code here// 首先找到要开始翻转的节点 定义一个虚拟头节点ListNode fakeHead new ListNode(0);fakeHead.next head;int length n - m 1;// 记录需要反转的节点个数// 记录原始链表中不需要被反转的的最后一个节点ListNode last fakeHead, cur head;while (m 1) {cur cur.next;last last.next;m--;}// 此时的 cur 节点为需要反转的头节点 pre 为原始链表中不需要被翻转的最后一个节点// lastOne 记录被反转链表的头节点也就是之后会成为尾节点ListNode pre null, next null, lastOne cur;while (length 0) {next cur.next;cur.next pre;pre cur;cur next;length--;}last.next pre;lastOne.next cur;return fakeHead.next;}
}思路
这道题开始有点晃到我了但是仔细分析指针移动的原则该记录就需要记录细心一点。 3、BM3 链表中的节点每k个一组翻转
题目描述 将给出的链表中的节点每 k 个一组翻转返回翻转后的链表。如果链表中的节点数不是 k 的倍数将最后剩下的节点保持原样。你不能更改节点中的值只能更改节点本身。 给定的链表是 1→2→3→4→5 对于 k2 , 你应该返回 2→1→4→3→5对于 k3 , 你应该返回 3→2→1→4→5 代码实现
public class BM3 {/*** param head ListNode类* param k int整型* return ListNode类*/public ListNode reverseKGroup(ListNode head, int k) {// write code hereListNode dummy new ListNode(0);dummy.next head;ListNode last dummy;// 已经翻转的链表的最后一个节点ListNode pre null, cur head, next null;// 每次找到下次要翻转的节点如果为空就不翻转while (cur ! null) {// 判断是否需要翻转本轮次ListNode hasNext cur;for (int i 1; i k; i) {hasNext hasNext.next;if (hasNext null) {return dummy.next;}}ListNode lastOne cur;for (int i 0; i k; i) {next cur.next;cur.next pre;pre cur;cur next;}last.next pre;last lastOne;lastOne.next next;}return dummy.next;}
}4、BM4 合并两个排序的链表
题目描述
输入两个递增的链表单个链表的长度为n合并这两个链表并使新链表中的节点仍然是递增排序的。如输入{1,3,5},{2,4,6}时合并后的链表为{1,2,3,4,5,6}所以对应的输出为{1,2,3,4,5,6}。0≤n≤1000−1000≤节点值≤1000
代码实现
public class BM4 {/*** param list1链表头1* param list2链表头2* return 返回新的头节点*/public ListNode Merge(ListNode list1, ListNode list2) {ListNode dummy new ListNode(0);// 采用虚拟头节点// 采用双指针遍历ListNode p1 list1, p2 list2, cur dummy;while (p1 ! null p2 ! null) {if (p1.val p2.val) {cur.next p1;p1 p1.next;} else {cur.next p2;p2 p2.next;}cur cur.next;}if (p1 ! null) {cur.next p1;}if (p2 ! null) {cur.next p2;}return dummy.next;}
}5、BM5 合并k个已排序的链表
题目描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
代码实现
public class BM5 {/*** 合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。** param lists 一个包含k个升序链表头节点的arrayList* return*/public ListNode mergeKLists(ArrayListListNode lists) {ListNode dummy new ListNode(0);// 虚拟头节点// 利用一个优先级队列PriorityQueueListNode queue new PriorityQueue((ListNode a, ListNode b) - {return a.val - b.val;});// 利用指针ListNode cur dummy;// 将arrayList中的头节点全部加入到优先级队列中for (ListNode listNode : lists) {if (listNode ! null) {queue.add(listNode);}}// 遍历while (!queue.isEmpty()) {ListNode poll queue.poll();cur.next poll;if ((poll poll.next) ! null) {queue.add(poll);}cur cur.next;}return dummy.next;}
}6、BM6 判断链表中是否有环
题目描述
判断给定的链表中是否有环。如果有环则返回true否则返回false。
代码实现
public class BM6 {/*** 判断给定的链表中是否有环。如果有环则返回true否则返回false。** param head 链表的头节点* return 返回真就是有环false无环*/public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false;}// 利用快慢指针法则ListNode fast head, slow head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {return true;}}return false;}
}7、BM7 链表中环的入口结点
题目描述
给一个长度为n链表若其中包含环请找出该链表的环的入口结点否则返回null。
代码实现
public class BM7 {public ListNode EntryNodeOfLoop(ListNode pHead) {// base caseif (pHead null || pHead.next null) {return null;}// 还是利用快慢指针ListNode fast pHead, slow pHead;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if (slow fast) {fast pHead;while (fast ! slow) {fast fast.next;slow slow.next;}return slow;}}return null;}
}8、BM8 链表中倒数最后k个结点
题目描述
输入一个长度为 n 的链表设链表中的元素的值为 ai 返回该链表中倒数第k个节点。如果该链表长度小于k请返回一个长度为 0 的链表。
代码实现
public class BM8 {/*** param pHead ListNode类* param k int整型* return ListNode类*/public ListNode FindKthToTail(ListNode pHead, int k) {if (pHead null) {return null;}// write code hereListNode dummy new ListNode(0);dummy.next pHead;ListNode slow dummy, fast dummy;while (k 0) {fast fast.next;k--;if (fast null) {return null;}}while (fast ! null) {fast fast.next;slow slow.next;}return slow;}
}9、BM9 删除链表的倒数第n个节点
题目描述
给定一个链表删除链表的倒数第 n 个节点并返回链表的头指针。
代码实现
public class BM9 {/*** param head ListNode类* param n int整型* return ListNode类*/public ListNode removeNthFromEnd(ListNode head, int n) {// write code hereListNode dummy new ListNode(0);dummy.next head;// 虚拟头节点ListNode pre dummy, cur head, fast head;while (n 0) {fast fast.next;n--;}while (fast ! null) {fast fast.next;cur cur.next;pre pre.next;}pre.next cur.next;return dummy.next;}
}10、BM10 两个链表的第一个公共结点
描述
输入两个无环的单向链表找出它们的第一个公共结点如果没有公共节点则返回空。注意因为传入数据是链表所以错误测试数据的提示是用其他方式显示的保证传入数据是正确的
代码实现
public class BM10 {/*** param pHead1* param pHead2* return 返回链表1和链表2的第一个公共节点*/public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {int length1 getLength(pHead1);int length2 getLength(pHead2);// 获取两个链表的长度差值int n length1 length2 ? length1 - length2 : length2 - length1;// 长短链表ListNode longHead length1 length2 ? pHead1 : pHead2;ListNode shortHead longHead pHead1 ? pHead2 : pHead1;// 让长的链表先走while (n 0) {longHead longHead.next;n--;}while (longHead ! null shortHead ! null) {if (longHead shortHead) {return longHead;}longHead longHead.next;shortHead shortHead.next;}return null;}// 得到链表的长度int getLength(ListNode head) {int size 0;while (head ! null) {size;head head.next;}return size;}
}11、BM11 链表相加(二)
题目描述
假设链表中每一个节点的值都在 0 - 9 之间那么链表整体就可以代表一个整数。例如链表 1 为 9-3-7链表 2 为 6-3最后生成新的结果链表为 1-0-0-0。
看到的第一眼没思路
之后硬写翻转后又翻转。。。。。
代码实现
public class BM11 {/*** param head1 ListNode类* param head2 ListNode类* return ListNode类*/public ListNode addInList(ListNode head1, ListNode head2) {// write code here// 翻转两个链表得到新的头节点ListNode reverseHead01 reverse(head1);ListNode reverseHead02 reverse(head2);// 新建链表int carry 0, sum 0;ListNode dummy new ListNode(0);ListNode cur dummy;while (reverseHead01 ! null || reverseHead02 ! null) {sum 0;if (reverseHead01 ! null) {sum reverseHead01.val;reverseHead01 reverseHead01.next;}if (reverseHead02 ! null) {sum reverseHead02.val;reverseHead01 reverseHead02.next;}sum carry;cur.next new ListNode(sum % 10);cur cur.next;carry sum / 10;}if (carry 1) {cur.next new ListNode(1);}return reverse(dummy.next);}ListNode reverse(ListNode head) {ListNode pre null, cur head, next null;while (cur ! null) {next cur.next;cur.next pre;pre cur;cur next;}return pre;}}12、BM12 单链表的排序
题目描述
给定一个节点数为n的无序单链表对其按升序排序。
思路
这道题有点难我不会看了题解才做出来的。根据题目中的要求空间复杂度为ON时间复杂度为ONlogN很容易联想到归并排序。将链表中的节点视为数组中的元素申请一个和链表长度大小相等的数组空间去存放链表中的元素。但是这种写法甚为暴力。
代码实现
public class BM12 {/*** param head ListNode类 the head node* return ListNode类*/public ListNode sortInList(ListNode head) {// write code here// 获取链表的长度申请一个大小为链表长度的数组空间存放链表中的所有元素int size getSize(head);ListNode[] nodes new ListNode[size];ListNode cur head;for (int i 0; i size; i) {nodes[i] cur;cur cur.next;}mergeSort(nodes, 0, size - 1);for (int i 0; i size - 1; i) {nodes[i].next nodes[i 1];}nodes[size - 1].next null;return nodes[0];}void mergeSort(ListNode[] arr, int start, int end) {if (start end) {int mid start (end - start) / 2;mergeSort(arr, start, mid);mergeSort(arr, mid 1, end);merge(arr, start, mid, end);}}void merge(ListNode[] arr, int left, int mid, int right) {ListNode[] help new ListNode[right - left 1];int index 0;int i left, j mid 1;while (i mid j right) {if (arr[i].val arr[j].val) {help[index] arr[i];} else {help[index] arr[j];}}while (i mid) {help[index] arr[i];}while (j right) {help[index] arr[j];}for (index 0; index right - left; index) {arr[left index] help[index];}}// 获取链表的长度int getSize(ListNode head) {int size 0;while (head ! null) {size;head head.next;}return size;}
}但是其实因为是链表所以可以使用快慢指针。
如果要使用快慢指针的话首先需要明白函数的递归含义。函数就是返回以head为头结点的初始链表排序后的新的链表的头节点。将原始链表分为两段有序的链表利用快慢指针然后将两段分别有序的链表合并成一段有序的链表并返回头节点。
代码实现 // 优美代码拒绝暴力求解// 返回以head为头节点的原始链表排好序后的链表新的头节点public ListNode sortInListNice(ListNode head) {// write code here// base caseif (head null || head.next null) {return head;}// 利用快慢指针进行找到中间位置将链表一分为二ListNode slow head, fast head.next;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}// 断掉分成两段链表ListNode rightHead slow.next;slow.next null;// 分别将两段链表进行排序ListNode left sortInListNice(head);ListNode right sortInListNice(rightHead);// 合并两个分别有序的链表return merge(left, right);}ListNode merge(ListNode left, ListNode right) {// 指针ListNode dummy new ListNode(0);ListNode cur dummy;while (left ! null right ! null) {if (left.val right.val) {cur.next left;left left.next;} else {cur.next right;right right.next;}cur cur.next;}if (left ! null) {cur.next left;}if (right ! null) {cur.next right;}return dummy.next;}13、BM13 判断一个链表是否为回文结构
题目
给定一个链表请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。
思路
这道题我还是不会。无语居然是用快慢指针将链表一分为二后翻转前半部分链表。行吧开干
代码实现
public class BM13 {/*** param head ListNode类 the head* return bool布尔型*/public boolean isPail(ListNode head) {// write code here// 利用快慢指针将链表一分为二ListNode slow head, fast head.next;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}// 斩断链表的联系if (fast ! null) {slow slow.next;}fast reverse(slow);slow head;while (slow ! null fast ! null) {if (slow.val ! fast.val) {return false;}fast fast.next;slow slow.next;}return true;}// 翻转链表返回头节点public ListNode reverse(ListNode head) {ListNode pre null, cur head, next null;while (cur ! null) {next cur.next;cur.next pre;pre cur;cur next;}return pre;}
}14、BM14 链表的奇偶重排
题目
给定一个单链表请设定一个函数将链表的奇数位节点和偶数位节点分别放在一起重排后输出。注意是节点的编号而非节点的数值。
代码实现
public class BM14 {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** param head ListNode类* return ListNode类*/public ListNode oddEvenList(ListNode head) {// write code hereif (head null || head.next null) {return head;}//ListNode evenHead head.next;ListNode odd head, even head.next;while (even ! null even.next ! null) {odd.next even.next;odd odd.next;even.next odd.next;even even.next;}odd.next evenHead;return head;}
}15、BM15 删除有序链表中重复的元素-I
题目
删除给出链表中的重复元素链表中元素从小到大有序使链表中的所有元素都只出现一次。
代码实现
public class BM15 {/*** param head ListNode类* return ListNode类*/public ListNode deleteDuplicates(ListNode head) {// write code hereif (head null || head.next null) {return head;}ListNode pre head, cur head.next;while (cur ! null) {while (cur ! null cur.val pre.val) {cur cur.next;}pre.next cur;pre cur;}return head;}
}16、BM16 删除有序链表中重复的元素-II
题目
给出一个升序排序的链表删除链表中的所有重复出现的元素只保留原链表中只出现一次的元素。
思路
还是不会所以写一下思路。需要删除的是只要重复出现过的元素采用递归去做。
代码实现
public class BM16 {/*** param head ListNode类* return 返回原始链表删除重复出现过的元素后的新的链表的头节点*/public ListNode deleteDuplicates(ListNode head) {// write code hereif (head null) {return null;}// 如果当前链表头节点和后面一个节点元素相等if (head.next ! null head.val head.next.val) {while (head.next ! null head.val head.next.val) {head head.next;}return deleteDuplicates(head.next);// 需要删除当前节点}head.next deleteDuplicates(head.next);return head;}
}总结
写了一下链表章节的题目对出现的十六道题目进行总结如下
反转链表重点在于指针的使用合理使用虚拟头节点指定区间内反转还是指针的使用。先找到需要开始翻转链表的头节点去这个链表中进行翻转。每K个一组进行翻转还是指针的使用需要记录下一组反转的起始位置这一组反转的位置。合并两个排序数组很简单。合并K个升序链表需要用到优先级队列。判断链表是否有环采用的是快慢指针。找到环形链表的入环节点还是快慢指针先判断有环相遇之后再去找到入环节点。链表的倒数最后K个结点还是利用指针一个先走然后再同时走。删除链表的倒数第N个节点还是采用的是关于指针先走后走。两个链表的第一个公共节点 先获取链表长度让长的链表先走。链表相加需要用的链表反转相加后再去翻转。单链表的排序根据空间复杂度可以联想到归并排序利用快慢指针将一个链表分为两个有序的链表然后合并两个有序的链表。判断链表是否为回文结构用的也是快慢指针将链表的后半部分进行翻转后再去判断是否为回文结构。奇偶重排还是利用指针删除有序链表的重复元素使得链表中所有的元素都只出现一次指针。删除有序链表中所有重复的元素使得链表中保留只出现一次的元素。这个很难采用的是递归方法做的判断当前节点元素和下一个节点元素是否相同。
