- 1华为ICT云赛道真题_华为ict云赛道题库
- 2FPGA的学习：数码管静态显示的实现（一）_fpga静态数码管显示
- 3[Mysql] 数据库基本概念
- 4mysql和redis备份和恢复数据的笔记
- 5IDEA中 配置 使用 SVN_idea配置svn
- 6spark中对rdd的几个操作_spark rdd有几种基本操作 分别列出几个典型的操作
- 7Windows Azure公有云服务相关方案
- 8yolov8跟踪模式部署Ros系统上，跟踪鼠标选择的目标，实时发布目标的坐标信息（python实现）_ros2 目标跟踪
- 9SpringSecurity系列学习(二):密码验证_springsecurity怎么看一个字符串是不是bcryptpasswordencoder编码
- 10对MaxKB进行个性化设置_maxkb图标修改
【数据结构刷题篇】链表篇_将单链表按基准划分
赞
踩
1.将单链表按值划分为链表左边小，中间相等，右边大的结构
题目分析：简单的来说就是把链表中的节点按照题目中给定话划分值target，给隔开，小于target的节点串到一块，等于target的节点串到一块，大于target的链表节点差混到一块。最后连接小于区，等于区，大于区，所断开的节点
思路1.0
解题思想：
1.遍历链表，计算出链表节点的个数，然后创建一个和链表长度相同节点类型的数组。
2.把链表中的各个节点都挨个放到数组中，然后对其进行荷兰国旗问题的求解。
那么什么是荷兰国旗问题呢？其实他一点都不神秘，也就是根据划分值，划分小于区，等于区，大于区而已。
荷兰国旗问题
我们不妨设现在有一个数组，数组中的元素为：4 ， 2 ，3 ，5 ，6 ，1 ，3 ， 0，给定的划分值为3
1.设置小于区，小于区初始下标为less = -1, 大于区等初始下标为more = array.length.
在index遍历数组时，遇到比划分值target大的元素，就把这个元素和大于区的前一个元素交换，交换之后原来在大于区前的元素，在index位置，此时index不能向后遍历，因为交换过来的值还没有和target进行比较，并且大于区向左进一步，
2.如果遇到了比target小的元素，就把这个元素和小于区前的第一个元素进行交换,并且小于区向右进一步 less++;
3.如果在遍历的过程中，遇到了和target相等的元素，就把index++,遍历下面的元素。
4.最后等到index == more的时候，遍历结束。
经过一系列操作后，就把数组成功的分成了3部分。
代码实现：
//交换代码 public void swap(Node []array,int left,int right){ Node temp = array[left]; array[left] = array[right]; array[right] = temp; } public void partition(Node []array, int val){ int less = -1; int more = array.length; int index = 0; while(index < more){ //如果划分值和在数组中遍历到的元素相同时index下标向右移动 if(array[index].val == val){ index++; //在数组中标遍历到的元素比划分值小，index向后移动，遍历到的这个元素和小于区的后一位元素交换 //index向后移动，小于区向后移动一位 }else if(array[index].val < val){ swap(array,index++,++less); //在数组中遍历到的元素比划值大，和大于区的前一个元素做交换，但是index下标不往后移动，因为交换之后是一个新值 //然后这个新值和划分值进行比较 }else if(array[index].val > val){ swap(array,index,--more); } } } public Node returnSpaceLinked(int val){ if(head == null){ return null; } //建一个 和链表等长的数组 Node []newArr = new Node[getLength(head)]; Node cur = head; int index = 0; while(cur != null){ newArr[index] = cur; cur = cur.next; index++; } partition(newArr,val); int i = 1; //连接链表 for(;i<newArr.length;i++){ newArr[i-1].next = newArr[i]; } newArr[i-1].next = null; return newArr[0]; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
思路2.0
其实这个思路，就和博主在开篇说的几乎一样，设置三个链表，一个链表中的节点时小于target的节点，把这些节点串起来，等于target的节点串起来，大于target的节点串起来。其实这样的做法还一定长上的减小了空间复杂度，孔家复杂度为O(1),思路一那种算法的空间复杂度为O(n),两种算法的时间复杂度都为O(n).
设置六个变量，SS，SE分别代表小于区链表的头节点和尾节点，MS，ME分别代表等于区的头节点和尾节点，ES，EE分别代表大于区的头节点和尾节点。
public Node returnSpaceLinkedTwo(Node head,int val){ if(head == null){ return null; } Node SS = null; Node SE = null; Node MS = null; Node ME = null; Node ES = null; Node EE = null; Node cur = head; Node curNext = null; while(cur != null){ curNext = cur.next; cur.next = null; if(cur.val < val){ if(SS == null){ SS = cur; SE = cur; }else{ //和尾节点连接 SE.next = cur; //更新尾节点 SE = cur; } }else if(cur.val == val){ if(MS == null){ MS = cur; ME = cur; }else{ ME.next = cur; ME = cur; } }else if(cur.val > val){ if(ES == null){ ES = cur; EE = cur; }else{ EE.next = cur; EE = cur; } } cur = curNext; } //现在小于区，等于区，大于区，已经建好了，但是怎样连接呢 //如果小于区不为空，判断等于区是否为空 if(SE != null){ SE.next = MS; //如果等于区等于空,就返回小于区的尾 //如果等于区为空，ME = SE ME = ME == null ? SE : ME; } if(ME != null){ ME.next = ES; } //如果小于区为空，等于区为空，返回大于区....... return SS == null ? (MS == null ? ES : MS):(SS); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
2.复制含有任意指针指向的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
思路1.0
题解一：其实我们可以利用哈希表，来存起链表中的每一个节点。把原来链表中的节点当成key值，然后所对应的value值时新建的节点但是这个节点所对应的数值域中的值为key值节点中的值。
通过map.get()方法得知value节点下一步串到那个节点。
代码展示：
public class Node { public int val; public Node rand; public Node next; public Node(int val){ this.val = val; } } public Node choneNode(Node head){ if(head == null){ return null; } Node cur = head; HashMap<Node,Node> map = new HashMap<>(); while(cur != null){ map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; //遍历链表 while(cur != null){ //得到链表中的value值的节点下一步要指向的节点 map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
思路2.0
题解二：
其实我们还可以这样做，在原链表的节点之间，增添一个节点，也就是这样的 1-----1!------2-----2!-------3-------3!------null-----null.
然后连接上1!,2 !,3!所对应的随机指针所对应的节点。然后断开1和1!等之间的连接。
代码展示：
public Node choneNodeNorHash(Node hhead){ if(head == null){ return null; } Node cur = head; Node curNext = null; //1.在原始的链表中添加克隆的节点 //1----2 //1--1`--2 while(cur != null){ //记录以前节点 curNext = cur.next; cur.next = new Node(cur.val); cur.next.next = curNext; cur = curNext; } //2.添加rand指针对应的节点 cur = head; Node cloneNode = null; while(cur != null){ curNext = cur.next.next; cloneNode = cur.next; cloneNode.rand = cur.rand == null ? null : cur.rand.next; cur = curNext; } //3.分离链表 cur = head; Node ret = cur.next; while(cur != null){ curNext = cur.next.next; cloneNode = cur.next; cur.next = curNext; cloneNode.next = curNext == null ? null : curNext.next; cur = curNext; } return ret; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
3.两个单链表相交的一系列问题
题目是这样的，两个不知道是有环，还是无环的链表，要求是，如果他们两个相交，就有一个相交节点，返回这个相交的节点。
1.子问题一：
链表是否有环，并返回入环节点。
判断链表是否有环，这个题目在博主以前的文章中提到。算了这里也请问的说一下吧。
第一使用快慢指针思想，
快慢指针，快指针一次走两步，慢指针一次走一步，如果链表有环，那么快慢指针就会相遇，然后一个节点从新指向原来的链表头节点。
这个节点从头节点开始出发，和快慢指针相遇节点，一步一块走，最终就会相遇。
第二使用hashSet方法。
hashSet方法，把链表中的每个节点都添加到hashSet中，如果出现了两个相同的节点，就可以肯定这个链表有环，这样也可以知道链表的入环节点。
快慢指针方法：
public Node isNodeCycle2(Node head){ if(head == null){ return null; } Node cur = head; Node fast = cur.next.next; Node slow = cur.next; while(fast != slow){ //没有环 if(fast.next == null || fast.next.next == null){ return null; } fast = fast.next.next; slow = slow.next; } slow = head; while(slow != fast){ slow = slow.next; fast = fast.next; } return slow; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
hashSet方法：
public Node isNodeCycle1(Node head){ if(head == null){ return null; } HashSet<Node> set = new HashSet<>(); Node cur = head; while(cur != null){ if(!set.contains(cur)){ set.add(cur); }else{ return cur; } cur = cur.next; } return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.子问题二：
如果两个链表没有环，那就成了，两个无环链表找相交节点。
这个问题，博主也在以前的文章中提到，在这里也说一下吧。
要得到两个非环形链表的相交节点，就要让两个链表在一个距离尾节点相同距离的节点开始遍历，不然两个节点始终不会相遇。
那么我们就要知道两个链表的长度差值。长链表先走差值步。
注意在遍历两个链表的时候，遍历到两个链表得到尾节点就可以了，即为cur.next != null，这样我们在遍历完链表之后，cur跟随节点，就走到了两个链表的尾节点，如果两个链表的尾节点不同，那么直接返回null.
然后从长链表的差值步开始，和短链表一块遍历，现在肯定是有相交节点的。
代码展示：
//判断两个非环形链表是否相交 public Node norCycleTogther(Node head1,Node head2){ if(head1 == null ||head2 == null){ return null; } Node cur1 = head1; int n = 0; while(cur1.next != null){ n++; cur1 = cur1.next; } Node cur2 = head2; while(cur2.next != null){ n--; cur2 = cur2.next; } //遍历到的两个链表的最后一个节点，如果这两个节点，不相同，直接返回null if(cur1 != cur2){ return null; } //然后得到长链表，短链表 cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; Math.abs(n); while(n != 0){ n--; cur1 = cur1.next; } while(cur1 != cur2){ cur1 = cur1.next; cur2 = cur2.next; } return cur1; } //如果两个链表都
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
3.子问题三：
如果一个链表有环，一个链表无环，这种情况是不会产生相交节点的。
如果两个链表都有环，找到两个链表的相交的节点
这种情况分为两种。
如图所示，第一种情况，两个环形链表的相交节点不在环上。
那么要得到相交节点就和链表中的环没有关系了，现在就等于说不要看环形，两个链表共用一个环，所以所两个链表的入环节点相同，如果两个链表的入环节点不相同，那么直接返回null,否则然后就和得到两个链表的相交节点思想相同。
第二种情况，两个环形链表的相交节点在环上。
从一个环形链表的入环节点的下一个节点开始遍历，如果在遍历环形链表的过程中，找到了另一个环形链表的入环节点，那么返回哪一个入环节点都可以。
//如果两个链表都是环形链表 public Node TwoCycle(Node head1,Node loop1,Node head2,Node loop2){ //入环之前，两个链表相交 int n = 0; Node cur1 = head1; Node cur2 = head2; if(loop1 == loop2){ while(cur1 != loop1){ n++; cur1 = cur1.next; } while(cur2 != loop2){ n--; cur2 = cur2.next; } cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2: head1; Math.abs(n); while(n != 0){ n--; cur1 = cur1.next; } while(cur1 != cur2){ cur1 = cur1.next; cur2 = cur2.next; } return cur1; }else{ Node cur = loop1.next; while(cur != loop1){ if(cur == loop2){ return loop2; } cur = cur.next; } } return null; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
代码总和：
public Node getIntersectionNode(Node head1,Node head2){
if(head1 == null || head2 == null){
return null;
}
//如果两个链表是有环节点
Node loop1 = isNodeCycle2(head1);
Node loop2 = isNodeCycle2(head2);
if(loop1 == null && loop2 == null){
return norCycleTogther(loop1,loop2);
}
if(loop1 != null && loop2 != null){
return TwoCycle(head1,loop1,head2,loop2);
}
return null;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
4.反转链表II
OJ链接
其实大家都知道反转链表很简单，但是这个题刻不一般哦。
反转的是链表中的部分链表，把子链表进行翻转，只有和原来在翻转链表之前，和之后的节点连接起来。
首先我们要找到翻转子链表的前一个节点fprev和后一个节点fend。在翻转子链表时，让翻转之前的子链表的头节点，指向fend,即 prev.next = fend，等到把子链表翻转之后，prev指向了子链表的最后一个节点。fprev.next = prev,然后让子链表的前一个节点，连到prev,这样就构成了一条链
class Solution { //反转部分链表 public ListNode reverseBetween(ListNode head, int left, int right) { int len = 0; ListNode fprev = null; ListNode fend = null; ListNode cur = head; while(cur != null){ len++; fprev = len == left - 1 ? cur : fprev; //得到翻转链表的前一个节点 fend = len == right + 1 ? cur : fend; //得到翻转链表的最后一个节点 cur = cur.next; } if(left > right || left > len || right > len){ return head; } //得到翻转链表的第一个节点 //如果返转链表前的第一个节点为null，那就是从主链表的第一个节点开始翻转 ListNode prev = fprev == null ? head : fprev.next; cur = prev.next; prev.next = fend;//连接节点 ListNode curNext = null;//标记节点 while(cur != fend){ curNext = cur.next; cur.next = prev; prev = cur; cur = curNext; } if(fprev != null){ fprev.next = prev; return head; } return prev; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
