网站域名空间管理,上海网站开发工程师招聘网,学校微信公众号怎么创建,网站运行时错误如何做#x1f495;轻舟已过万重山#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;算法系列–链表刷题(二) 今天为大家带来的是算法系列--链表刷题(二),带来了几道经典的有关链表的面试题(合并K个有序列表) 1.两数相加 https://leetcode.cn/problems/a… 轻舟已过万重山 作者Mylvzi 文章主要内容算法系列–链表刷题(二) 今天为大家带来的是算法系列--链表刷题(二),带来了几道经典的有关链表的面试题(合并K个有序列表) 1.两数相加 https://leetcode.cn/problems/add-two-numbers/ 模拟两数相加:
使用两个指针cur1和cur2来遍历两个链表,通过t记录每次相加的结果,最后创建出新的节点,尾插
注意:
每次相加时都需要更新t的值,但是不可以直接将t设置为0,因为存在进位的可能,比如t 9 9 18,要插入节点的val 8,还要记录进位1,所以:val t % 10, t / 10循环的结束要同时满足三个条件,cur1 null, cur2 null, t 0,其中最后t 0这种情况最容易忘记,导致最后需要进位没进位成,结果相比于正确答案少了一位 代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 l1;ListNode cur2 l2;ListNode phead new ListNode(0);ListNode cur phead;// 用于尾插int t 0;// 用于表示本次相加的结果 处理进位// 要注意t最后可能不为0 要进一位while(cur1 ! null || cur2 ! null || t ! 0) {// 加上第一个节点if(cur1 ! null) {t cur1.val;cur1 cur1.next;}// 加上第二个节点if(cur2 ! null) {t cur2.val;cur2 cur2.next;}ListNode newNode new ListNode(t % 10);t / 10;// 尾插cur.next newNode;cur newNode;}return phead.next;}
}2.两两交换链表中的节点 https://leetcode.cn/problems/swap-nodes-in-pairs/description/ 思路:
分别得到下标为奇数的所有节点的组合和下标为偶数的所有节点的组合(下标从1开始)按照偶数节点在前,奇数节点在后的顺序合并两个链表得到新的链表
代码实现:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head null || head.next null) return head;// 定义两个虚拟节点 分别接收奇数和偶数的节点ListNode p1 new ListNode(0);ListNode p2 new ListNode(0);ListNode cur1 p1;ListNode cur2 p2;ListNode cur head;int i 1;// 分别得到奇数和偶数的链表组合while(cur ! null) {ListNode newNode new ListNode(cur.val);if(i % 2 ! 0) {// 奇数cur1.next newNode;cur1 newNode;}else {// 偶数cur2.next newNode;cur2 newNode;}cur cur.next;i;}// 合并两个链表ListNode p3 new ListNode(0);ListNode t1 p1.next;ListNode t2 p2.next;ListNode cur3 p3;while(t1 ! null || t2 ! null) {if(t2 ! null) {cur3.next t2;cur3 t2;t2 t2.next;}if(t1 ! null) {cur3.next t1;cur3 t1;t1 t1.next;}}return p3.next;}
}注:本题更加简洁的写法是通过递归实现的,感兴趣的可以去我的算法系列里查看
3.重排链表 https://leetcode.cn/problems/reorder-list/ 思路:
首先获得中间节点,以中间节点为基准,分为两个不同的链表l1和l2逆序l2合并两个链表 代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public void reorderList(ListNode head) {ListNode slow head, fast head;// 找到中间节点while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}ListNode l1 head;ListNode l2 slow.next;slow.next null;// 逆序第二个节点l2 reverseList(l2);ListNode phead new ListNode(0);ListNode cur phead;// 合并两个链表while(l1 ! null || l2 ! null) {if(l1 ! null) {cur.next l1;cur l1;l1 l1.next;}if(l2 ! null) {cur.next l2;cur l2;l2 l2.next;}}head phead.next;}public ListNode reverseList(ListNode head) {if(head null) return null;if(head.next null) return head;ListNode pHead new ListNode(0);ListNode cur head;while(cur ! null) {ListNode curNext cur.next;cur.next pHead.next;pHead.next cur;cur curNext;}return pHead.next;}
}同样的本题也有更加简洁的递归写法
4.合并 K 个升序链表hard
链接: https://leetcode.cn/problems/merge-k-sorted-lists/description/
分析: 思路一:利用优先级队列 其实本题和合并两个有序链表很相似,可以看做是上一题的plus版本
虽然这里是合并K个有序链表,但是我们可以借鉴合并两个有序链表的思路,创建一个傀儡节点,找到两个链表节点的最小值,依次插入到傀儡节点之后
这里的难点在于如果只有两个节点,我们可以直接比较,但是现在有K个节点,如何快速地找到K个节点的最小值呢?使用优先级队列,利用优先级队列将K个链表的头结点存入到优先级队列之中,由于默认是小根堆,所以堆顶元素就是K个链表头结点的最大值,将其插入到傀儡节点之后,更新傀儡节点,然后插入堆顶节点的下一个节点,接着判断最小值,重复上述过程
手写: 代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode heap new PriorityQueue((o1,o2) -o1.val - o2.val);ListNode ret new ListNode(0);ListNode phead ret;for(ListNode head : lists)// 将链表的头结点存入堆中if(head ! null)heap.offer(head);while(!heap.isEmpty()) {ListNode tmp heap.poll();phead.next tmp;phead tmp;if(tmp.next ! null) heap.offer(tmp.next);// 注意下一个节点可能为空}return ret.next;}
}思路二:利用归并的思想 其实这道题非常符合分治归并的思想,题目相当于给了我们一个比较特殊的数组(数组的元素是链表),实际上最重要完成的工作就是对这K个元素进行从小到大的排序,既然是排序我们就可以使用归并的思想,为什么想到归并呢?这是经过分析得到的,实际上我们是对一个一个的链表进行合并排序操作的,这一步其实就是归并中分解到最小单元,开始回并的过程啊!所以可以使用归并的思想解决
代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists null || lists.length 0) return null;// 采用归并的思想解决return merge(lists,0,lists.length-1);}public ListNode merge(ListNode[] lists,int left,int right) {// 递归出口if(left right) return lists[left];int mid (left right) /2;ListNode l1 merge(lists,left,mid);ListNode l2 merge(lists,mid 1,right);return mergeTwoLists(l1,l2);}// 合并两个有序链表public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 递归if(list1 null) return list2;if(list2 null) return list1;if(list1.val list2.val) {list1.next mergeTwoLists(list1.next,list2);return list1;}else {list2.next mergeTwoLists(list2.next,list1);return list2;}}
}5.K个⼀组翻转链表
链接: https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
分析:
本题采用模拟的思想,具体的模拟策略如下:
求出要反转多少个长度为K的链表–n翻转n次即可 代码:
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 求需要翻转的组数nint cnt 0;ListNode tmp head;while(tmp ! null) {cnt;tmp tmp.next;}int n cnt / k;// 开始进行翻转ListNode ret new ListNode(0);ListNode phead ret;ListNode cur head;for(int i 0; i n; i) {ListNode prev cur;// 保存当前翻转链表的头结点for(int j 0; j k; j) {ListNode curnext cur.next;cur.next phead.next;phead.next cur;cur curnext;}phead prev;// 每翻转完一组就更新phead}phead.next cur;return ret.next;}
}
