寿宁县建设局网站,公司介绍网站怎么做的,wordpress的nginx404,品牌网站建设小7蝌蚪文章目录1.翻转链表2.链表内指定区间翻转3. 链表中的节点每k个一组翻转4. 合并两个排序的链表5. 合并k个排序的链表6. 判断链表是否有环7. 链表中倒数第k个节点8. 删除链表中的倒数第k和节点9. 两个链表的第一个公共节点10.链表的入环节点11. 链表相加#xff08;二#xff0…
文章目录1.翻转链表2.链表内指定区间翻转3. 链表中的节点每k个一组翻转4. 合并两个排序的链表5. 合并k个排序的链表6. 判断链表是否有环7. 链表中倒数第k个节点8. 删除链表中的倒数第k和节点9. 两个链表的第一个公共节点10.链表的入环节点11. 链表相加二12. 单链表排序13.判断一个链表是否是回文结构14. 链表的奇偶重排15.删除有序链表中重复的元素I16.删除有序链表中重复的元素||1.翻转链表 ❤️❤️ 算法思路 设置一个指针pre这个pre指向的是工作节点也就是在链表中挨个遍历的cur的前一个节点初始的时候设置pre指向为null因为要翻转链表链表中的最后一个节点指向为null。逐个遍历链表中的每一个节点每次遍历节点的前一个节点。curNext cur.next 然后节点指定翻转当前节点指向前一个节点 cur.next pre,然后更新pre的指向指向为cur 即 pre cur 然后工作节点cur 继续遍历链表的后续节点。
//翻转链表
public Node reverse(Node head){if(head null || head.next null){return head;}Node cur head;Node curNext null;Node pre null;while (cur ! null){//记录当前节点的后置节点curNext cur.next;//当前节点的next指针指向前置节点那么此时就实现了一个节点的翻转cur.next pre;//前置节点指向更新pre cur;//当前节点继续遍历cur curNext;}//.最后cur 为空pre是cur 的前置节点那么此时的pre就是翻转后链表的头节点return pre;
}2.链表内指定区间翻转 ❤️❤️ 算法思路 其实就是翻转链表的一个变种翻转链表的一部分找到翻转链表的头节点和尾节点还有就是翻转链表头节点的前一个节点和翻转链表的最后一个节点的后一个节点。把部分链表翻转之后进行拼接。
//翻转链表中的一部分
public Node reverseSub(Node head,int m,int n){if(head null || head.next null || m n){return head;}Node dummy new Node(-1);dummy.next head;Node pre dummy;//得到翻转链表的头节点的前一个节点for(int i 0;i m - 1;i){pre pre.next;}//翻转链表的最后一个节点Node rightNode pre;for(int i 0; i n - m 1;i){rightNode rightNode.next;}//翻转链表的头节点Node leftNode pre.next;pre.next null;System.out.println(rightNode.val);Node curNext rightNode.next;rightNode.next null;reverse(leftNode);pre.next rightNode;leftNode.next curNext;return dummy.next;
}3. 链表中的节点每k个一组翻转 ❤️❤️ 算法思路 因为要翻转链表那么我们可以联想到使用栈栈是先进后出的那么此时我们把节点添加到栈中等到栈中添了k个节点之后然后我们把这些节点依次从栈中取出来并且连接每个节点那么这就反转了一组链表片段。如果在遍历链表的时候如果这一组不够k个那么我们就直接把剩下的几个节点添加到反转链表的末尾即可
public Node kCountsReverse(Node head,int k){if(head null || head.next null) {return head;}//使用栈把链表中的节点压到栈中进栈的时候一边计数如果此时的这个计数的结果等于k 那么就退出把栈中的节点弹出来//并且连接在一起。如果不够k个一组那么就直接拼到翻转链表的后面StackNode stack new Stack();Node dummy new Node(-1);Node p dummy; //添加后续节点while(true){int count 0;Node cur head;while(cur ! null count ! k){stack.push(cur);count;cur cur.next;}//如果不构成一组,但是此时cur nullif(count ! k){//直接拼接p.next head;break;}while(!stack.empty()){p.next stack.pop();p p.next;}p.next cur;head cur;}return dummy.next;
}4. 合并两个排序的链表 ❤️❤️ 算法思路 首先判定先决条件如果在待排序的链表中有一个链表为空那么就直接返回另一个链表如果两个链表都为空那么就直接输出null。如果两个链表都不为空那么就进行排序设置一个虚拟节点dummy,然后设置一个连接链表的指针p,这个指针p用来遍历整个链表起先这个指针p指向节点dummy.
public Node sort(Node head1,Node head2){if(head1 null head2 null){return null;}if(head1 null){return head2;}if(head2 null){return head1;}Node dummy new Node(-1);Node p dummy;Node cur1 head1;Node cur2 head2;while(cur1 ! null cur2 ! null){if(cur1.val cur2.val){p.next cur1;cur1 cur1.next;}else{p.next cur2;cur2 cur2.next;}p p.next;}if(cur1 ! null){p.next cur1;}if(cur2 ! null){p.next cur2;}return dummy.next;
}5. 合并k个排序的链表
两种方法方法一使用归并排序方法二:使用堆
❤️❤️算法思路方法一使用归并排序思想根据归并排序思想我们把这k个链表一直分一直分分到 这个组合有两个链表我们两个链表进行合并然后再返回排序好的链表。总的来说就是先分后合。这里我们可以把每个链表看成一个元素就是list之间进行分治然后在合并
public Node func(ListNode list){if(list null){return null;}return process(list,0,list.size() - 1);
}
public Node process(ListNode list,int left,int right){if(left right){return null;}else if(left right){return list.get(left);}int mid (left right) 1; Node head1 process(list,left,mid);Node head2 process(list,mid 1,right);//调用上面我们写的排序两个已经排序好的链表中的那个题目的代码return sort(head1,head2);
}❤️❤️**算法思路方法二**使用优先队列。其实我们在题目中可以不进行指定创建出来的queue对象是小顶堆其实创建出来的queue对象默认就是一个小顶堆。就是把这k个链表的头节点都加到小顶堆中让每个链表的头节点进行比较在小顶堆中值域较小的节点就在堆顶然后我们创建出一个虚拟节点用于来连接排序好的链表还有设置指针p.如果小顶堆不为空那么就的弹出小顶堆的堆顶元素并且保存堆顶元素使用指针p 连接弹出的这个节点然后判断弹出的这个节点有没有后继节点如果有就添加到小顶堆中。继续使用小顶堆找出最小的节点使用p指针继续拼接
public Node func2(ListNode list){if(list null){return null;}PriorityQueueNode queue new PriorityQueue((v1,v2)-(v1.val - v2.val));//把每个链表的头节点都加到小跟堆中for(int i 0;i list.size();i){//如果k个链表中的头节点不为空那么就把这个节点添加到小跟堆中if(list.get(i) ! null){queue.offer(list.get(i));}}Node dummy new Node(-1);Node p dummy;while(!queue.isEmpty()){//如果此时的小跟堆不为空那么此时就弹出堆中最小的元素也就是堆顶元素Node node queue.poll();p.next node;p p.next;//如果堆顶元素在链表中还有下一个节点那么就把下一个节点添加到小顶堆中继续下一次比较if(node.next ! null){queue.offer(node.next);}}return dummy.next;
}6. 判断链表是否有环 ❤️❤️算法思路 其实这是一个非常经典的面试题这个题目考察的是快慢指针起初让快慢指针同时位于链表的头节点然后遍历链表让慢指针一次遍历一个节点让快指针一次遍历两个节点(跳跃两个节点)如果是环形链表那么此时的快指针和慢指针一定会在某一个位置相遇
public boolean isCycle(Node head){if(head null){return false;}if(head.next null) {return true;}Node slow head;Node fast head;while(fast.next ! null fast.next.next ! null){slow slow.next;fast fast.next.next;if(slow fast){return true; }}return false;
}7. 链表中倒数第k个节点 ❤️❤️算法思想 设置两个指针一个是快指针一个是慢指针先让快指针遍历k步那么此时的慢指针和快指针之间就相差k个节点那么此时让慢指针和快指针一块遍历链表一次遍历一个节点直到快指针指向的节点为null,那么此时的慢指针就指向了链表的倒数第k个节点
ublic Node func2(Node head,int k){//设置一个指针先让这个快指针走k步然后设置一个慢指针快指针和慢指针一块走知道快指针遍历到了null节点//那么此时就找到了链表的倒数第k个节点Node slow head;Node fast head;int count 0;while(count ! k){if(fast ! null){count;fast fast.next;}else{return null;}}while(fast ! null){slow slow.next;fast fast.next;}return slow;
}8. 删除链表中的倒数第k和节点 ❤️❤️算法思路 首先我们要设置一个虚拟节点然后让这个虚拟节点的next指针指向头结点因为在题目中有可能删除头结点。然后我们和上题是一样的设置两个指针一个快指针一个慢指针快指针先遍历k步因为我们最终要找到的是删除节点的前一个节点然后让这前一个节点的next指针指向删除节点的后一个节点。所以此时我们的循环条件就由原来的fast ! null 变成了 fast.next ! null 这样快指针和慢指针一次走一步然后直到fast.next null 那么我们此时就找到了链表的倒数第k 1 个节点就是删除节点的前一个节点然后它的next指针指向删除节点的后一个节点。
public Node func3(Node head,int k){if(head null){return null;}Node dummy new Node(-1);dummy.next head;Node slow dummy;Node fast dummy;for(int i 0;i k;i){fast fast.next;}while(fast.next ! null){slow slow.next;fast fast.next;}slow.next slow.next.next;return dummy.next;
}9. 两个链表的第一个公共节点 ❤️❤️ 算法思路 首先得到两个链表的长度让长的链表减去短的链表的长度得到的差值让长链表走差值步然后两个链表中的指着一步一个走知道两个链表的节点重合
public Node func4(Node head1,Node head2){if(head1 null || head2 null){return null;}int count1 getCount(head1);int count2 getCount(head2);int num Math.abs(count1 - count2);if(count1 count2){while(num ! 0){head1 head1.next;num--;}}else{while(num ! 0){head2 head2.next;num--;}}while(head1 ! head2){head1 head1.next;head2 head2.next;}return head1;
}10.链表的入环节点 ❤️❤️算法思想 首先判断链表是否有环如果链表是无环的那么就不存在这个链表的入环节点然后就是当快指针和慢指针走到一块的时候此时就记住这个节点然后让慢指针指向链表的头部然后两个指针一块走直到两个指针相遇。
public Node getCycle(Node head){Node slow head;Node fast head;while(fast.next ! null fast.next.next ! null){slow slow.next;fast fast.next.next;if(slow fast){return slow;}}return null;
}
public Node cycleNode(Node head){if(head null || head.next null){return null;}Node fast getCycle(head);if(fast null){return null;}Node slow head;while(slow ! fast){slow slow.next;fast fast.next;}return slow;
}11. 链表相加二 ❤️❤️算法思想 其实就相当于是两个数字在相加数字在相加的时候是从个位开始相加的那么我们此时只有把链表翻转之后才能相加并且在相加的时候要注意进位相加完之后得到翻转的结果之后把链表进行翻转
public Node getSum(Node head1,Node head2){if(head1 null head2 null){return null;}if(head1 null){return head2;}if(head2 null){return head1;}int carry 0;//翻转链表Node newHead1 reverse(head1);Node newHead2 reverse(head2);Node dummy new Node(-1);Node p dummy;while(newHead1 ! null || newHead2 ! null){int sum (newHead1 null ? 0 : newHead1 .val) (newHead2 null ? 0 : newHead2.val) carry;carry sum 10 ? sum / 10 : 0;sum sum 10 ? sum % 10 : sum;Node node new Node(sum);p.next node;p p.next;newHead1 newHead1 null ? null : newHead1.next;newHead2 newHead2 null ? null : newHead2.next;}if(carry ! 0){p.next new Node(carry);}return reverse(dummy.next);
}12. 单链表排序 ❤️❤️算法思想 其实这个题还是很简单的我们可以改成归并排序其实这个归并排序思想就是把链表从中间分开每次都进行分知道把链表分成单个的节点然后在里用两个有序链表构成一个新的有序的大链表就行了。这个就是典型的归并排序。
public class Solution {/*** * param head ListNode类 the head node* return ListNode类*/public ListNode sortInList (ListNode head) {//保证时间复杂度为O(n * logn)if(head null || head.next null){return head;}//每次都断开中间节点ListNode temp getMid(head);ListNode head1 sortInList(head);ListNode head2 sortInList(temp);return marge(head1,head2);}private ListNode marge(ListNode head1, ListNode head2) {ListNode dummy new ListNode(-1);ListNode p dummy;while(head1 ! null head2 ! null){if(head1.val head2.val){p.next head1;head1 head1.next;} else{p.next head2;head2 head2.next;}p p.next;}if(head1 ! null){p.next head1;}if(head2 ! null){p.next head2;}return dummy.next;}private ListNode getMid(ListNode head) {ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next ! null){slow slow.next;fast fast.next.next;}ListNode temp slow.next;slow.next null;return temp;}
}13.判断一个链表是否是回文结构 ❤️❤️算法思想找到链表的中间节点把中间节点之后的链表节点全部翻转然后让一个指针指向链表的头节点让一个指针指向翻转链表的头节点然后两个指针一个向右遍历一个向左遍历在遍历的过程中判断节点中的val值是否是相同的。
public class Solution {/**** param head ListNode类 the head* return bool布尔型*/private ListNode getMid(ListNode head) {ListNode slow head;ListNode fast head;while(fast.next ! null fast.next.next ! null){slow slow.next;fast fast.next.next;}return slow;}//方法二翻转部分链表public boolean isPail (ListNode head) {if(head null){return false;}//找到链表的中间节点ListNode preNewHead getMid(head);ListNode newHead preNewHead.next;preNewHead.next null;ListNode cur reverse(newHead);while(head ! null cur ! null){if(head.val ! cur.val){return false;}head head.next;cur cur.next;}return true;}private ListNode reverse(ListNode head) {ListNode pre null;ListNode cur head;while(cur ! null){ListNode curNext cur.next;cur.next pre;pre cur;cur curNext;}return pre;}
}
14. 链表的奇偶重排 ❤️❤️算法思想 首先呢这是一种笨办法我们把原链表中所有的全部节点添加到栈中并且把每个节点之前的连接断开在栈中添加节点的时候我们还要进行奇数要知道在栈中得到了多少个节点然后设置两个虚拟节点和两个遍历指针p1,p2然后我们把栈中的节点弹出来根据此时的count判断此时这个是偶数位节点和时奇数位节点然后拼好两个链表然后把两个链表进行翻转然后两个链表拼接。
public static Node func2(Node head){StackNode stack new Stack();Node dummy1 new Node(-1);Node p1 dummy1;Node dummy2 new Node(-2);Node p2 dummy2;Node cur head;int count 0;while(cur ! null){Node curNext cur.next;cur.next null;stack.push(cur);count;cur curNext;}while(count ! 0){//奇数if(count % 2 1){p1.next stack.pop();p1 p1.next;}else{//偶数p2.next stack.pop();p2 p2.next;}count--;}//因为此时的两个链表是有栈得到的那么此时它们的排列顺序是不对的那么此时我们把这两个链表进行翻转Node node1 reverse(dummy1.next);Node node2 reverse(dummy2.next);Node ret node1;while(node1.next ! null){node1 node1.next;}//得到奇数链表的最后一个节点和偶数链表的最后一个节点相连node1.next node2;return ret;
}15.删除有序链表中重复的元素I ❤️❤️算法思想先判断该链表是不是一个空链表如果是空链表那么就直接返回null,如果该链表只有一个节点那么就直接返回head。因为要删除相同的节点并且保留重复节点中的一个节点那现在就比如说此时有 cur,cur.next这个两个指针指向的节点这两个节点的值域中的val是一样的那么此时我们就保留cur这个位置上的节点删除cur.next这个指针指向的节点。判断当前节点和当前节点的下一个节点相同那么此时我们就不在返回的链表上添加这个节点。
图示
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//如果此时的头节点为空或者是此时只有一个节点if(head null || head.next null){return head;}//设置虚拟节点因为在删除元素的时候可能会对于头节点有影响ListNode dummy new ListNode(-1);ListNode p dummy;ListNode cur head;while(cur ! null){//如果在遍历的时候遇到了相同的节点那么此时就一直遍历不在返回链表中插入新的节点if(cur.next ! null cur.val cur.next.val){while(cur.next ! null cur.val cur.next.val){cur cur.next;}}p.next cur;cur cur.next;p p.next;}//dummy.next表示的是返回链表的头节点return dummy.next;}
}16.删除有序链表中重复的元素|| ❤️❤️算法思想其实这道题是上一道题的一个延伸就是把链表中重复的的节点都删除了。那么此时我们就把预先设置的虚拟节点看做为要返回链表的头节点令工作节点cur dummy 判断cur.next 和 cur.next.next是不是相同的节点然后记录一下这两个节点的值在判断cur.next.next之后有没有相同的节点如果有cur.next cur.next.next.
图示
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {if(head null || head.next null){return head;}ListNode dummy new ListNode(-1);ListNode cur dummy;dummy.next head;while(cur.next ! null cur.next.next ! null){if(cur.next.val cur.next.next.val){int x cur.next.val;while(cur.next ! null cur.next.val x){cur.next cur.next.next;}}else{cur cur.next;}}return dummy.next;}
}
