力扣刷题日记/day7/2022.6.29

Java链表基础学习

Java类构造方法

构造方法是类的一种特殊方法，用来初始化类的一个新的对象，在创建对象（new 运算符）之后自动调用。Java 中的每个类都有一个默认的构造方法，并且可以有一个以上的构造方法。

Java 构造方法有以下特点：

• 方法名必须与类名相同

• 可以有 0 个、1 个或多个参数

• 没有任何返回值，包括 void

• 默认返回类型就是对象类型本身

• 只能与 new 运算符结合使用

构造方法不能被 static、final、synchronized、abstract 和 native（类似于 abstract）修饰。 

public class MyClass {
    private int m;    // 定义私有变量
    MyClass() {
        // 定义无参的构造方法
        m = 0;
    }
    MyClass(int m) {
        // 定义有参的构造方法
        this.m = m;
    }
}

 

//以下是leetcode上的源代码，
//注释是类结构知识点的复习
* public class ListNode {    
 *     int val;    //节点值
 *     ListNode next;    //ListNode类型指针，指向下一个节点
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//用java定义实现的链表结构，ListNode本质上是一个java类，具有类所具有的特性，创建对象;通过对象访问类的成员变量和成员方法
//ListNode中存在三个构造方法，构造方法和类名必须相同
//当然了，ListNode也有泛型，使用泛型可以兼容不同的的数据类型
 	class ListNode<E>{                //类名 ：Java类就是一种自定义的数据结构
	    E val;                        //数据 ：节点数据 
		ListNode<E> next;             //对象 ：引用下一个节点对象。在Java中没有指针的概念,Java中的引用和C语言的指针类似
		ListNode(E val){              //构造方法 ：构造方法和类名相同   
    		this.val=val;             //把接收的参数赋值给当前类的val变量
	    }
    }

 java类的定义加public与不加public的区别及应用

public ListNode mergeTwoLists （）{}
//定义一个方法，方法名是mergeTwoLists，返回值的类型是ListNode

public calss solution{}
//加public表示全局类，该类可以import到任何类内。不加public默认为保留类，只能被同一个包内的其他类引用

//值得注意的是public class 虽然可以被任何类访问，但若是所访问类中的方法不加public或者static，将会出现一个warning，所以当要访问其他包中的public类中的方法，则需要加上public或者static才能进行访问。

 例题：

 递归法：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        } else if(list2 == null){
            return list1;
        } else if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        } else{
            list2.next = mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}

//头节点默认为首结点
//list1.val=head.val
//采用了递归思想
思路
我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：也就是说，两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
我们直接将以上递归过程建模，同时需要考虑边界情况。
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。

迭代法：

思路：当list1和list2都不是空链表时，判断list1和list2的头节点值的大小，将较小的值放在结果链表中，一个节点放在结果链表中后，将对应链表的节点向后移动一位。

算法：

首先设置一个哨兵节点prehead（-1），链表合并完成后，直接返回prehead.next即可，维护一个prev指针;

ListNode prev = prehead        //ListNode prev表示prev的类型是ListNode类型，

在接下来的判断中，调整prev的指针位置和prev的位置，如果list1当前的节点值(val)小于list2的节点值，把list1当前的节点接在prev节点的后面(prev.next=list1)，同时list1指针向后移一位(list1=list1.next)，否则，对list2做同样的改变。不管我们移动list1，list2的指针位置，prev的位置都要向后移一位(prev=prev.next)

在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);    //哨兵节点

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}