Nowcodertop7-11 - continuous updating

TOP7 The entry node of a link in a list

/** * 7  The entry node of a link in a list  *  Suppose that there is a total of a individual , The nodes in the ring are b individual , set up fast The number of nodes passed by the pointer is f,slow The number of nodes passed by the pointer is s, Then there are two conclusions ： * f = 2 * s （ That is, the number of nodes passed by the fast pointer must be twice that of the slow pointer ） * f = s + nb （ When the two meet , Quick, the pointer must have gone around n circle ） *  From the above two equations, we can get ,f = 2nb,s = nb *  So we know , When two hands meet , The slow pointer has gone nb Step , It is known that we are going to the entry node , Need to go a + kb Step , And then s = nb Just go again a You can reach the entrance , Let's move the fast pointer  *  End node , Then the two pointers go back step by step , When they meet, the location is the entry node  * step 1： The way to judge whether there are rings in the linked list is to judge whether there are rings in the linked list , And find the node that meets . * step 2： The slow pointer continues to meet the node , Quick pointer back to the chain header , The two pointers synchronously start to traverse the linked list element by element . * step 3： The place where we meet again is the entrance of the ring . **/
public class top7 {
    
    // Judge if there is a ring , Return to where you met 
    public ListNode hasCycle(ListNode head) {
    
        // First judge if the linked list is empty 
        if (head == null) return null;
        // Fast slow double pointer 
        ListNode fast = head;
        ListNode slow = head;
        // If there is no ring, the fast pointer will go to the end of the list first 
        while (fast != null && fast.next != null) {
    
            // Move the pointer two steps 
            fast = fast.next.next;
            // Move the slow pointer one step 
            slow = slow.next;
            // There is a ring when you meet , Return to where you met 
            if (fast == slow) return slow;
        }
        // To the end, there is no ring , return null
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    
        ListNode slow = hasCycle(pHead);
        // No ring 
        if (slow == null) return null;
        // Quickly return the pointer to the meter 
        ListNode fast = pHead;
        // Meeting again is the ring entrance 
        while (fast != slow) {
    
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

TOP8 Last in the list k Nodes

/** * 8  Last in the list k Nodes  * step 1： Prepare a quick pointer , From the head of the chain , Go first on the list k Step . * step 2： Prepare the slow pointer to point to the original chain header , Represents the current element , Then the distance between the slow pointer and the fast pointer is always k. * step 3： The speed pointer moves synchronously , When the fast pointer reaches the end of the list , The slow pointer just counts down k The location of the elements . **/
public class top8 {
    
    public ListNode FindKthToTail (ListNode pHead, int k) {
    
        ListNode fast = pHead;
        ListNode slow = pHead;
        //  Let's go first  K  Step 
        for (int i = 0; i < k; i++) {
    
            if (fast != null) fast = fast.next;
            //  It indicates that the length of the linked list is less than  K
            else return null;
        }
        //  When the fast pointer is not empty , The speed pointer advances synchronously 
        while (fast != null) {
    
            fast = fast.next;
            slow = slow.next;
        }
        //  The fast pointer is null , That's all , The slow pointer points to the penultimate  k  Location of nodes 
        return slow;
    }
}

TOP9 Delete the last of the linked list n Nodes

public class Solution {
    
    /** * @param head ListNode class  * @param n int integer  * @return ListNode class  */
    public ListNode removeNthFromEnd (ListNode head, int n) {
    
        //  Add header , To save it , To prevent modification 
        //  Return to the next node in the header 
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        ListNode fast = head;
        ListNode slow = head;
        //  Let the fast pointer go forward first k Step 
        for(int i = 0; i < n ; i++) {
    
            if(fast != null) fast = fast.next;
            //  It indicates that the length of the linked list is less than k
            else return null;
        }
        while(fast != null) {
    
            fast = fast.next;
            pre = pre.next;
            slow = slow.next;
        }
        //  At this time, the fast pointer has reached null , The node pointed by the slow pointer is the node to be deleted 
        pre.next = slow.next;
        return res.next;
    }
}

TOP10 The first common node of two linked lists

public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
// ListNode l1 = pHead1;
// ListNode l2 = pHead2;
// while(l1 != l2) {
    
// l1 = (l1 == null) ? pHead2 : l1.next;
// l2 = (l2 == null) ? pHead1 : l2.next;
// }
// return l1;
        
        //  Calculate the length of two linked lists 
        int len1 = length(pHead1);
        int len2 = length(pHead2);
        //  If the length of two linked lists is different , Those with more nodes go first , Until they are the same length 
        while(len1 != len2) {
    
            if(len1 > len2) {
    
                pHead1 = pHead1.next;
                len1 --;
            }else {
    
                pHead2 = pHead2.next;
                len2 --;
            }
        }
        //  At this time, the length of the two linked lists is equal , Compare its element size 
        while(pHead1 != pHead2) {
    
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        // Go to the end , In the end, there are two possibilities , One is head1 It's empty ,
        // In other words, they don't intersect . Another possibility is that head1
        // Not empty , in other words head1 It's their intersection 
        return pHead1;
    }
    private int length(ListNode head) {
    
        int n = 0;
        while(head != null) {
    
            head = head.next;
            n++;
        }
        return n;
    }
}

TOP11 Add the linked list ( Two )

public class Solution {
    
    /** * @param head1 ListNode class  * @param head2 ListNode class  * @return ListNode class  */
    public ListNode addInList (ListNode head1, ListNode head2) {
    
        if(head1 == null) return head2;
        if(head2 == null) return head1;
        ListNode l1 = reverse(head1);
        ListNode l2 = reverse(head2);
        ListNode res = null;
        int c = 0; //  carry 
        //  If  c > 0  Then it means that there is a carry and a node has to be inserted 
        while(l1 != null || l2 != null || c > 0) {
    
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int total = v1 + v2 + c; // The sum of the current one 
            c = total / 10;
            //  Insert the current node 
            ListNode temp = new ListNode(total % 10); //  Current bit 
            temp.next = res;
            res = temp;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return res;
    }
    
    //  Flip list 
    public ListNode reverse(ListNode head) {
    
        if(head == null) return null;
        ListNode pre = null;
        while(head != null) {
    
            ListNode next  = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}