• 售前

  • 售后

热门帖子
入门百科

【数据结构刷题篇】链表篇

[复制链接]
忆神姆原们 显示全部楼层 发表于 2022-1-12 12:43:41 |阅读模式 打印 上一主题 下一主题
文章目录



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部分。

代码实现:
  1.       //交换代码
  2.      public void swap(Node []array,int left,int right){
  3.         Node temp = array[left];
  4.         array[left] = array[right];
  5.         array[right] = temp;
  6.     }
  7.     public void partition(Node []array, int val){
  8.         int less = -1;
  9.         int more = array.length;
  10.         int index = 0;
  11.         while(index < more){
  12.             //如果划分值和在数组中遍历到的元素相同时index下标向右移动
  13.             if(array[index].val == val){
  14.                 index++;
  15.                 //在数组中标遍历到的元素比划分值小,index向后移动,遍历到的这个元素和小于区的后一位元素交换
  16.                 //index向后移动,小于区向后移动一位
  17.             }else if(array[index].val < val){
  18.                 swap(array,index++,++less);
  19.                 //在数组中遍历到的元素比划值大,和大于区的前一个元素做交换,但是index下标不往后移动,因为交换之后是一个新值
  20.                 //然后这个新值和划分值进行比较
  21.             }else if(array[index].val > val){
  22.                 swap(array,index,--more);
  23.             }
  24.         }
  25.     }
  26.      public Node returnSpaceLinked(int val){
  27.         if(head == null){
  28.             return null;
  29.         }
  30.         //建一个 和链表等长的数组
  31.         Node []newArr = new Node[getLength(head)];
  32.         Node cur = head;
  33.         int index = 0;
  34.         while(cur != null){
  35.             newArr[index] = cur;
  36.             cur = cur.next;
  37.             index++;
  38.         }
  39.         partition(newArr,val);
  40.         int i = 1;
  41.         //连接链表
  42.         for(;i<newArr.length;i++){
  43.             newArr[i-1].next = newArr[i];
  44.         }
  45.         newArr[i-1].next = null;
  46.         return newArr[0];
  47.     }
复制代码

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节点下一步串到那个节点。
代码展示:
  1. public Node returnSpaceLinkedTwo(Node head,int val){
  2.         if(head == null){
  3.             return null;
  4.         }
  5.         Node SS = null;
  6.         Node SE = null;
  7.         Node MS = null;
  8.         Node ME = null;
  9.         Node ES = null;
  10.         Node EE = null;
  11.         Node cur = head;
  12.         Node curNext = null;
  13.         while(cur != null){
  14.             curNext = cur.next;
  15.             cur.next = null;
  16.             if(cur.val < val){
  17.                 if(SS == null){
  18.                     SS = cur;
  19.                     SE = cur;
  20.                 }else{
  21.                     //和尾节点连接
  22.                     SE.next = cur;
  23.                     //更新尾节点
  24.                     SE = cur;
  25.                 }
  26.             }else if(cur.val == val){
  27.                 if(MS == null){
  28.                     MS = cur;
  29.                     ME = cur;
  30.                 }else{
  31.                     ME.next = cur;
  32.                     ME = cur;
  33.                 }
  34.             }else if(cur.val > val){
  35.                 if(ES == null){
  36.                     ES = cur;
  37.                     EE = cur;
  38.                 }else{
  39.                     EE.next = cur;
  40.                     EE = cur;
  41.                 }
  42.             }
  43.             cur = curNext;
  44.         }
  45.         //现在小于区,等于区,大于区,已经建好了,但是怎样连接呢
  46.         //如果小于区不为空,判断等于区是否为空
  47.         if(SE != null){
  48.             SE.next = MS;
  49.             //如果等于区等于空,就返回小于区的尾
  50.             //如果等于区为空,ME = SE
  51.              ME = ME == null ? SE : ME;
  52.         }
  53.         if(ME != null){
  54.             ME.next = ES;
  55.         }
  56.         //如果小于区为空,等于区为空,返回大于区.......
  57.         return SS == null ? (MS == null ? ES : MS):(SS);
  58.     }
复制代码
思路2.0

题解二:
其实我们还可以这样做,在原链表的节点之间,增添一个节点,也就是这样的 1-----1!------2-----2!-------3-------3!------null-----null.

然后连接上1!,2 !,3!所对应的随机指针所对应的节点。然后断开1和1!等之间的连接。
代码展示:
  1. public class Node {
  2.     public int val;
  3.     public Node rand;
  4.     public Node next;
  5.     public Node(int val){
  6.         this.val = val;
  7.     }
  8. }
  9. public Node choneNode(Node head){
  10.         if(head == null){
  11.             return null;
  12.         }
  13.         Node cur = head;
  14.         HashMap<Node,Node> map = new HashMap<>();
  15.         while(cur != null){
  16.             map.put(cur, new Node(cur.val));
  17.             cur = cur.next;
  18.         }
  19.         cur = head;
  20.         //遍历链表
  21.         while(cur != null){
  22.         //得到链表中的value值的节点下一步要指向的节点
  23.             map.get(cur).next = map.get(cur.next);
  24.             map.get(cur).rand = map.get(cur.rand);
  25.             cur = cur.next;
  26.         }
  27.         return map.get(head);
  28.     }
复制代码

3.两个单链表相交的一系列问题

题目是这样的,两个不知道是有环,还是无环的链表,要求是,如果他们两个相交,就有一个相交节点,返回这个相交的节点。
1.子问题一:

链表是否有环,并返回入环节点。
判断链表是否有环,这个题目在博主以前的文章中提到。算了这里也请问的说一下吧。
第一使用快慢指针思想
快慢指针,快指针一次走两步,慢指针一次走一步,如果链表有环,那么快慢指针就会相遇,然后一个节点从新指向原来的链表头节点。
这个节点从头节点开始出发,和快慢指针相遇节点,一步一块走,最终就会相遇。
第二使用hashSet方法。
hashSet方法,把链表中的每个节点都添加到hashSet中,如果出现了两个相同的节点,就可以肯定这个链表有环,这样也可以知道链表的入环节点。
快慢指针方法:
  1. public Node choneNodeNorHash(Node hhead){
  2.         if(head == null){
  3.             return null;
  4.         }
  5.         Node cur = head;
  6.         Node curNext = null;
  7.         //1.在原始的链表中添加克隆的节点
  8.         //1----2
  9.         //1--1`--2
  10.         while(cur != null){
  11.             //记录以前节点
  12.             curNext = cur.next;
  13.             cur.next = new Node(cur.val);
  14.             cur.next.next = curNext;
  15.             cur = curNext;
  16.         }
  17.         //2.添加rand指针对应的节点
  18.         cur = head;
  19.         Node cloneNode = null;
  20.         while(cur != null){
  21.             curNext = cur.next.next;
  22.             cloneNode = cur.next;
  23.             cloneNode.rand = cur.rand == null ? null : cur.rand.next;
  24.             cur = curNext;
  25.         }
  26.         //3.分离链表
  27.         cur = head;
  28.         Node ret = cur.next;
  29.         while(cur != null){
  30.             curNext = cur.next.next;
  31.             cloneNode = cur.next;
  32.             cur.next = curNext;
  33.             cloneNode.next = curNext == null ? null : curNext.next;
  34.             cur = curNext;
  35.         }
  36.         return ret;
  37.     }
复制代码
hashSet方法:
  1. public Node isNodeCycle2(Node head){
  2.         if(head == null){
  3.             return null;
  4.         }
  5.         Node cur = head;
  6.         Node fast = cur.next.next;
  7.         Node slow = cur.next;
  8.         while(fast != slow){
  9.             //没有环
  10.             if(fast.next == null || fast.next.next == null){
  11.                 return  null;
  12.             }
  13.             fast = fast.next.next;
  14.             slow = slow.next;
  15.         }
  16.         slow = head;
  17.         while(slow != fast){
  18.             slow = slow.next;
  19.             fast = fast.next;
  20.         }
  21.         return slow;
  22.     }
复制代码

2.子问题二:

如果两个链表没有环,那就成了,两个无环链表找相交节点。
这个问题,博主也在以前的文章中提到,在这里也说一下吧。
要得到两个非环形链表的相交节点,就要让两个链表在一个距离尾节点相同距离的节点开始遍历,不然两个节点始终不会相遇。
那么我们就要知道两个链表的长度差值。长链表先走差值步。
注意在遍历两个链表的时候,遍历到两个链表得到尾节点就可以了,即为cur.next != null,这样我们在遍历完链表之后,cur跟随节点,就走到了两个链表的尾节点,如果两个链表的尾节点不同,那么直接返回null.
然后从长链表的差值步开始,和短链表一块遍历,现在肯定是有相交节点的。
代码展示:
  1.      public Node isNodeCycle1(Node head){
  2.         if(head == null){
  3.             return null;
  4.         }
  5.         HashSet<Node> set = new HashSet<>();
  6.         Node cur = head;
  7.         while(cur != null){
  8.             if(!set.contains(cur)){
  9.                 set.add(cur);
  10.             }else{
  11.                 return cur;
  12.             }
  13.             cur = cur.next;
  14.         }
  15.         return null;
  16.     }
复制代码

3.子问题三:

如果一个链表有环,一个链表无环,这种情况是不会产生相交节点的。
如果两个链表都有环,找到两个链表的相交的节点
这种情况分为两种。

如图所示,第一种情况,两个环形链表的相交节点不在环上
那么要得到相交节点就和链表中的环没有关系了,现在就等于说不要看环形,两个链表共用一个环,所以所两个链表的入环节点相同,如果两个链表的入环节点不相同,那么直接返回null,否则然后就和得到两个链表的相交节点思想相同。
第二种情况,两个环形链表的相交节点在环上
从一个环形链表的入环节点的下一个节点开始遍历,如果在遍历环形链表的过程中,找到了另一个环形链表的入环节点,那么返回哪一个入环节点都可以。
  1. //判断两个非环形链表是否相交
  2.     public Node norCycleTogther(Node head1,Node head2){
  3.         if(head1 == null ||head2 == null){
  4.             return null;
  5.         }
  6.         Node cur1 = head1;
  7.         int n = 0;
  8.         while(cur1.next != null){
  9.             n++;
  10.             cur1 = cur1.next;
  11.         }
  12.         Node cur2 = head2;
  13.         while(cur2.next != null){
  14.             n--;
  15.             cur2 = cur2.next;
  16.         }
  17.         //遍历到的两个链表的最后一个节点,如果这两个节点,不相同,直接返回null
  18.         if(cur1 != cur2){
  19.             return  null;
  20.         }
  21.         //然后得到长链表,短链表
  22.         cur1 = n > 0 ? head1 : head2;
  23.         cur2 =  cur1 == head1 ? head2 : head1;
  24.         Math.abs(n);
  25.         while(n != 0){
  26.             n--;
  27.             cur1 = cur1.next;
  28.         }
  29.         while(cur1 != cur2){
  30.             cur1 = cur1.next;
  31.             cur2 = cur2.next;
  32.         }
  33.         return cur1;
  34.     }
  35.     //如果两个链表都
复制代码
代码总和:
  1.      //如果两个链表都是环形链表
  2.     public Node TwoCycle(Node head1,Node loop1,Node head2,Node loop2){
  3.         //入环之前,两个链表相交
  4.         int n = 0;
  5.         Node cur1 = head1;
  6.         Node cur2 = head2;
  7.         if(loop1 == loop2){
  8.             while(cur1 != loop1){
  9.                 n++;
  10.                 cur1 = cur1.next;
  11.             }
  12.             while(cur2 != loop2){
  13.                 n--;
  14.                 cur2 = cur2.next;
  15.             }
  16.             cur1 = n > 0 ? head1 : head2;
  17.             cur2 = cur1 == head1 ? head2: head1;
  18.             Math.abs(n);
  19.             while(n != 0){
  20.                 n--;
  21.                 cur1 = cur1.next;
  22.             }
  23.             while(cur1 != cur2){
  24.                 cur1 = cur1.next;
  25.                 cur2 = cur2.next;
  26.             }
  27.             return cur1;
  28.         }else{
  29.             Node cur = loop1.next;
  30.             while(cur != loop1){
  31.                 if(cur == loop2){
  32.                     return loop2;
  33.                 }
  34.                 cur = cur.next;
  35.             }
  36.         }
  37.         return null;
  38.     }
复制代码

4.反转链表II

OJ链接

其实大家都知道反转链表很简单,但是这个题刻不一般哦。
反转的是链表中的部分链表,把子链表进行翻转,只有和原来在翻转链表之前,和之后的节点连接起来。
首先我们要找到翻转子链表的前一个节点fprev和后一个节点fend。在翻转子链表时,让翻转之前的子链表的头节点,指向fend,即 prev.next = fend等到把子链表翻转之后prev指向了子链表的最后一个节点fprev.next = prev,然后让子链表的前一个节点,连到prev,这样就构成了一条链

  1. public Node getIntersectionNode(Node head1,Node head2){
  2.         if(head1 == null || head2 == null){
  3.             return null;
  4.         }
  5.         //如果两个链表是有环节点
  6.         Node loop1 = isNodeCycle2(head1);
  7.         Node loop2 = isNodeCycle2(head2);
  8.         if(loop1 == null && loop2 == null){
  9.             return norCycleTogther(loop1,loop2);
  10.         }
  11.         if(loop1 != null && loop2 != null){
  12.             return TwoCycle(head1,loop1,head2,loop2);
  13.         }
  14.         return null;
  15.     }
复制代码
来源:https://blog.caogenba.net/qq_54883034/article/details/122412291
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作