做网站好还是做程序员好,以网站内容建设和运维为主,贵阳seo公司,汉庭酒店网站建设方案概述
链表的题目没有太难的算法#xff0c;纯看熟练度#xff0c;是必须会。面试笔试不会是直接挂的#xff0c;或者给面试官留下不好的印象。 单双链表的反转#xff0c;单链表实现队列#xff0c;K个一组反转链表。
单链表反转
链表节点的定义
Data
public class Li…概述
链表的题目没有太难的算法纯看熟练度是必须会。面试笔试不会是直接挂的或者给面试官留下不好的印象。 单双链表的反转单链表实现队列K个一组反转链表。
单链表反转
链表节点的定义
Data
public class ListNodeT {public T val;public ListNodeT next;ListNode() {}ListNode(T val) { this.val val; }ListNode(T val, ListNodeT next) { this.val val; this.next next; }// 链表对数器// 用数组创建单链表public static T ListNodeT build(T[] arr){if(arr null || arr.length 0){return null;}// 创建虚拟头节点ListNodeT dummy new ListNode();ListNodeT cur dummy;for (T item : arr) {cur.next new ListNode(item);cur cur.next;}return dummy.next;}// 重写toString方法Overridepublic String toString(){StringBuilder sb new StringBuilder();sb.append(this.val);ListNodeT next this.next;while (next ! null){sb.append( - ).append(next.val);next next.next;}return sb.toString();}
}单链表反转leetcode: https://leetcode.cn/problems/reverse-linked-list/description/ /*** 单链表的反转* a hrefhttps://leetcode.cn/problems/reverse-linked-list/description/.../a* null-1-2-3-4-5* pre null* head 1* next head.next* head.next pre* pre head* head next* 先记住下一个值然后改变指针方向。然后pre和head各流转到下一个值*/public ListNode reverseList(ListNode head){if(head null){return head;}ListNode pre null;ListNode next null;while(head ! null) {next head.next;head.next pre;pre head;head next;}return head;}双链表的反转
双链表节点的定义
public class DoubleNodeV {V val;DoubleNodeV next;DoubleNodeV last;DoubleNode() {}DoubleNode(V val) { this.val val; }DoubleNode(V val, DoubleNodeV next, DoubleNodeV last) { this.val val; this.next next; this.last last;}}双链表反转
/*** 双链表的反转* -* 思路和单链表一样只不过是多了一个指针。* 先记住下一个值然后改变指针方向。然后pre和head各流转到下一个值*/public DoubleNode reverseDoubleList(DoubleNode head){if(head null){return head;}DoubleNode pre null;DoubleNode next null;while(head ! null) {next head.next;head.next pre;head.last next;pre head;head next;}return head;}单链表实现队列
class MyQueueV{// head记录队列的头节点private ListNodeV head;// tail记录队列的尾节点private ListNodeV tail;// 队列大小private int size;// 判空public boolean isEmpty(){return this.size 0;}// 获取队列长度public int size(){return this.size;}/*** 元素压入队列* 更新head,tail,size* 思路* 压入第一个元素比如1那么head1tail1;* 压入第二个元素比如2那么1-2即head1, tail2;* 压入第三个元素比如3那么1-2-3即head1, tail3;* ...* 压入第i个元素比如i那么1-2-3...-i即head1taili;* 每次压入元素时原来的tail元素指向新压入的元素。即tail.next cur;* tail都会更新即tail cur;* param value 元素*/public void offer(V value){ListNodeV cur new ListNode(value);if(tail null){head cur;tail cur;}else{tail.next cur;tail cur;}size;}/*** 元素弹出队列* 遵循队列先进先出的特点所以每次弹出的都是队列的head* 思路* 如果队列不为空* 比如当前队列是1-2-3-4-5head1tail5;* 此时弹出那么head会更新head head.next;** 如果队列为空* 那么head null; 此时注意tail要和head保持一致否则会出现headnull但是tail5的情况*/public V poll(){V res null;if(head ! null){res head.val;head head.next;size--;}else{tail head;}return res;}// 返回队列头部元素public V peek(){if(head ! null){return head.val;}return null;}}K个一组反转链表
力扣hard: https://leetcode.cn/problems/reverse-nodes-in-k-group/description/ step1 返回第k个元素
public static ListNode getKGroupEnd(ListNode start, int k){int count 1;while(count k start ! null){start start.next;count;}return start;}step2 : 反转链表
public static void reverse(ListNode start, ListNode end){// 反转的while循环边界 cur ! end.nextend end.next;// 反转链表经典3指针ListNode cur start;ListNode pre null;ListNode next null;// 先记录下一节点指针反转。precur指针流转到下一节点while (cur ! end){next cur.next;cur.next pre;pre cur;cur next;}// 反转完成后再改变起始节点的next指针start.next end;}step3: 完整流程。拼接各组的操作。 public static ListNode reverseKGroup(ListNode head, int k){// 先找到第一组的k个节点ListNode start head;ListNode end getKGroupEnd(start, k);if(end null){// 不够k个所以直接返回return head;}// 记录head并且head不会再改变了head end;reverse(start, end);ListNode lastEnd start;// 循环找剩下的while(lastEnd.next ! null){start lastEnd.next;end getKGroupEnd(start, k);if(end null){// 不够k个所以直接返回return head;}reverse(start, end);// 和上一组连接起来lastEnd.next end;lastEnd start;}return head;}
