LeetCode 25K 个一组翻转链表&26删除排序数组中的重复项

简介: 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

K个一组翻转链表



题目要求


给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。


示例:

给你这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5


说明:

你的算法只能使用常数的额外空间。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。


分析:

本题是K个一组进行翻转,相信大家都有遇到翻转链表实现起来可能容易一些,但是这里面要求K个一组进行翻转,不满足K个就不翻转。并且要求必须交换节点不能创建新的节点。如果K=3,从宏观来看需要交换的可能是这样的:


20200913200155429.png


而具体的一个交换流程该如何考虑呢?一组一组的交换,当组是否还满足K个?如何实现?


  • 用两个指针,一个指针tail预先走K步,如果能正常行走说明可以翻转。


每一组翻转需要整个联立起来,该如何实现呢?可以预先记录首尾,然后再翻转局部将整个链表串联起来。在具体的交换步骤,可以使用一个prenode记录前驱节点以实现交换。


20200913203559203.png


具体实现的代码为:


 public  ListNode reverseKGroup(ListNode head, int k) {
      if(head==null)return null;
          ListNode value=new ListNode(0);
      value.next=head;
      ListNode pretail=value;//前一个区间末尾
      ListNode pretailNext=value.next;//交换区间的第一个(交换后会变成最后一个需要连接下一个区间)
      ListNode tail=head;//末尾用来试探
      ListNode preNode=null;//记录前驱节点
      ListNode node=head;//当前节点
      int index=0;
      while(tail!=null)
      {
        while (index++<k) {//拉开K个程度
               if(tail==null)//不满足反转条件直接返回
          return value.next;
          tail=tail.next;
        }//tail到达固定位置
        while (index-->1) {//开始反转node
          //System.out.println(index+" "+head.val);
        node=head;
        head=head.next;
        node.next=preNode;
        preNode=node;
        }
        //连接
        pretail.next=node;
        pretailNext.next=tail;
        pretail=pretailNext;
        pretailNext=tail;
        index=0;
      }
      return value.next;  
    }


删除排序数组中的重复项


描述:

给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。


示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。


示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。


说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。


你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝

int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。

// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。

for (int i = 0; i < len; i++) {

print(nums[i]);

}


分析:


这题很简单,用一个index标记当前位置,用i遍历判断是否和前一个相等,如果相等不操作,不相等就重新存入,最后这个index返回即可,当然,虽然是个int类型的函数,但是题目要求存到数组中会判定数组的,需要存一下。


实现代码为:


public int removeDuplicates(int[] nums) {
     int index=1;
     for(int i=1;i<nums.length;i++)
     {
       if(nums[i]!=nums[i-1])
       {
          nums[index++]=nums[i];
       }
     }
     return index;
   }


好了,本次打卡结束,如果有兴趣欢迎关注公众号:bigsai,回复进群加入一起打卡。

目录
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
48 0
Leetcode第21题(合并两个有序链表)
|
1月前
leetCode(删除有序数组中的重复项)
如何在不使用额外空间的情况下,通过双指针法原地删除有序数组中的重复项。
33 2
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
46 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
1月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
77 0
|
1月前
|
存储
一篇文章了解区分指针数组,数组指针,函数指针,链表。
一篇文章了解区分指针数组,数组指针,函数指针,链表。
18 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行