[数据结构与算法]数组与链表的两种模型

过滤器模型 循环数组 筛选条件

输入数组nums? ?

int?n?=0;

? ? for(int?i?=0;?i<?nums.length;?i++){

?????????if?(条件){

?????????nums[n]?=?nums[i];

?????????n++;

????????}

????}

实战leetcode26题

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

class?Solution?{

????public?int?removeDuplicates(int[]?nums)?{

????????int?n?=0;

????????for(int?i?=0;?i<?nums.length;?i++){

????????????if?(i==0?||?nums[i-1]?!=?nums[i]){

????????????nums[n]?=?nums[i];

????????????n++;

????????}

????}

????????return?n;
}

????}

}

88 题 合并数组

class?Solution?{

????public?void?merge(int[]?nums1,?int?m,?int[]?nums2,?int?n)?{

????????int?i?=?m-1,j?=?n-1;

????????for?(int?k?=?m+n-1;?k>=0;?k--)?{

????????????if?(j<0?||?(i>=0?&&?nums1[i]>nums2[j])){

????????????????nums1[k]=nums1[i];

????????????????i--;

????????????}else?{

????????????????nums1[k]=nums2[j];

????????????????j--;

????????????}

????????}

????}

}

此题可以逆方向考虑 以免重复删除nums1里面的数组，因为是有两个数组所以我们可以考虑以k来记录所得数组位置

2.反转链表模型

leetcode206

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        while(head!=null){
            ListNode headNext = head.next;
            head.next=last;
            last = head;
            head = headNext;
        }
        return last;

    }
}

headNext 用来记录之前的head 使其不被丢失然后交换next 和 head 注意尾部对应的head.next对应空值 所以以空值开头

最后以此模型记录一道hard题目

leetcode025? k组一个反转列表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode protect = new ListNode(0, head);
        ListNode last = protect;
        while(head!=null){
            ListNode end = getEnd(head,k);
            if(end == null) break;
            ListNode nextGrop = end.next;
            reverseList(head,nextGrop);

            last.next = end;
            head.next = nextGrop;

            last =head;
            head = nextGrop;
            

        }
        return protect.next;
    }
        ListNode getEnd(ListNode head,int k){
            while(head != null){
                k--;

                if(k==0){
                    return head;
                }
                head = head.next;
            }
            return null;
        }
    void reverseList(ListNode head,ListNode stop){
            ListNode last = head;
            head = head.next;
            while(head != stop){
            ListNode headNext = head.next;
            head.next=last;
            last = head;
            head = headNext;
            }
        }
    }

分三步完成，首先因为是k组我们需要对其进行分组，如果剩余数组达不到k则不反转，所以我们先getEnd找到一组里面最后一个值用node告诉计算机反转到这个值就不用反转了

第二步是反转 使用上述模型 写一个反转方法

第三步 找到下一组切换头部为下一组数据开头