Li Kou brush question diary /day7/2022.6.29

Java Linked list basic learning

Java Class constructor

A constructor is a special method of a class , A new object used to initialize a class , Creating objects （new Operator ） And then automatically call .Java Each class in has a default constructor , And there can be more than one construction method .

Java The construction method has the following characteristics ：

• The method name must be the same as the class name

• There can be 0 individual 、1 Two or more parameters

• No return value , Include void

• The default return type is the object type itself

• Only with new Operators are used in conjunction with

The construction method cannot be static、final、synchronized、abstract and native（ Be similar to abstract） modification . 

public class MyClass {
    private int m;    //  Define private variables 
    MyClass() {
        //  Define the construction method without parameters 
        m = 0;
    }
    MyClass(int m) {
        //  Define a construction method with parameters 
        this.m = m;
    }
}

 

// Here are leetcode Source code on ,
// Notes are the review of knowledge points of class structure 
* public class ListNode {    
 *     int val;    // Node values 
 *     ListNode next;    //ListNode Type a pointer , Point to next node 
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
// use java Define the linked list structure of the implementation ,ListNode It's essentially a java class , Have the characteristics of a class , Create objects ; Access the member variables and member methods of the class through objects 
//ListNode There are three construction methods in , The constructor and class name must be the same 
// Yes, of course ,ListNode There are also generics , Using generics can be compatible with different data types 
 	class ListNode<E>{                // Class name  ：Java Class is a custom data structure 
	    E val;                        // data  ： Node data  
		ListNode<E> next;             // object  ： Reference the next node object . stay Java There is no concept of pointer in ,Java And C Language pointers are similar to 
		ListNode(E val){              // Construction method  ： The construction method is the same as the class name    
    		this.val=val;             // Assign the received parameter to the current class val Variable 
	    }
    }

 java Class definition plus public With or without public The difference and application of

public ListNode mergeTwoLists （）{}
// Define a method , The name of the method is mergeTwoLists, The type of return value is ListNode

public calss solution{}
// Add public Represents a global class , This class can import Into any class . No addition public The default is reserved class , Can only be referenced by other classes in the same package 

// It is worth noting that public class  Although it can be accessed by any class , But if the method in the visited class does not add public perhaps static, There will be a warning, So when you want to access other packages public Methods in class , You need to add public perhaps static In order to access .

  Example ：

  Recursive method ：

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;
        }
    }
}

// The head node defaults to the first node 
//list1.val=head.val
// Recursion is adopted 
 Ideas 
 We can recursively define... In two linked lists as follows  merge  operation （ Ignore the boundary case , For example, empty linked list ）： in other words , The node with the smaller head value of the two linked lists is the same as that of the remaining elements  merge  Operation result merging .
 Let's model the recursive process directly , At the same time, we need to consider the boundary conditions .
 If  l1  perhaps  l2  It started with an empty list  , So no operations need to be merged , So we just need to return a non empty list . otherwise , We need to judge  l1  and  l2  Which list's head node has a smaller value , Then recursively determine the next node to add to the result . If one of the two linked lists is empty , Recursion ends .

Iterative method ：

Ideas ： When list1 and list2 Is not an empty list , Judge list1 and list2 The size of the head node value of , Put smaller values in the result linked list , A node is placed in the result linked list , Move the node of the corresponding linked list backward by one bit .

Algorithm ：

First set up a The sentinel node prehead（-1）, After the list merging , Go straight back to prehead.next that will do , Maintain a prev The pointer ;

ListNode prev = prehead        //ListNode prev Express prev The type is ListNode type ,

In the next judgment , adjustment prev Pointer position and prev The location of , If list1 Current node value (val) Less than list2 Node value , hold list1 The current node is connected to prev After the node (prev.next=list1), meanwhile list1 Move the pointer back one bit (list1=list1.next), otherwise , Yes list2 Make the same change . No matter how we move list1,list2 Pointer position of ,prev All positions should be moved backward (prev=prev.next)

At the end of the cycle , l1 and l2 At most one is not empty . Because the two input lists are ordered , So no matter which list is not empty , It contains all the elements larger than all the elements in the previously merged linked list . This means that we just need to simply connect the non empty list to the back of the merged list , And return to the merge list .

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);    // The sentinel node 

        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;
        }

        //  After the merger  l1  and  l2  At most, only one has not been merged yet , We can directly point the end of the linked list to the list that has not been merged 
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}