Blue eucalyptus has met the locust bird, I don't love everything but you

Hello everyone, this is the new one, please take care of me🙈🙉🙊. In this blog, Xinyi will introduce the second bullet of the blasting force button - linked list OJ question, which is full of dry goods. (The following results are all in IDEA) I hope that it can help everyone while facilitating their own review. 😜😜😜🥇🥈🥉

Without further ado, let's jump right into our article.

1. 🥇 Delete duplicate nodes in the linked list

Question link: Delete duplicate nodes in linked list
This time we want to delete all duplicate nodes in the linked list (none of them are kept), then we must traverse the linked list
And what we want to return is the head of the linked list after the change. It is much better for us to create a virtual node. Just connect the unrepeated elements to the virtual node. Note: There are many details to judge the repetition.

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = pHead;

        while (cur != null){
            if (cur.next != null && cur.val == cur.next.val){//Duplicate nodes may be at the last node
                while (cur.next != null && cur.val == cur.next.val){//Too many duplicate nodes continue to the last node
                    cur = cur.next;
                }
                cur = cur.next;//Skip the tail of duplicate nodes
            } else{
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;//empty tail
        return newHead.next;
    }
}

2. 🥇 Palindrome linked list

Question link: Palindromic linked list
At first glance, this question seems to be a bit difficult to solve. Don't panic, don't panic, we observe its structure, and it is not difficult to find that we must start from the middle, so how to judge? Remember how we talked about the fast and slow pointer method last time, we used it to find the middle node, and at the same time used a puppet node to plug the first half of the head. When the middle is reached, we exit the loop and start judging the palindrome.

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
       if (A == null){
            return false;
        }
        
        ListNode fast = A;
        ListNode slow = A;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = A;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            cur = cur.next;
            slow.next = tmp;
            tmp = slow;
            slow = cur;
        }
        
        while (slow != null){
            if (slow.val != tmp.val){
               return false;
            }
            slow = slow.next;
            tmp = tmp.next;
        }
        return true;
    }
}

3. 🥇 Circular linked list

Question link: circular linked list

To judge there is a ring? Traverse to find the last node? How to find it? If there is a ring, the last node cannot be found. So what's up with Gao? Remember our fast and slow pointer method? In real life, we know that on a lap of the track, the fast one will definitely meet the slow one (over a lap), in fact, we already have an idea: fast moves twice at a time Step, slow takes one step at a time, if you meet, there will be a loop, some friends may ask if fast can take three steps? In some cases this is not possible, such as:

You can test it yourself.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
}

4. 🥇 Circular linked list II

Question link: Ring List II

We have already mentioned the circular linked list I above, so how to find the entry point? Here is a mathematical problem involved, here is a new one to help you analyze it slowly:

We set the distance from the starting point to the entry point to be x, the distance from the encounter point to the entry point to be y, and the perimeter of the ring to be C:

We know that fast is twice as fast as slow, so fast travels twice as far as slow. And slow will collide with at most one lap, while fast may run n laps

Distance traveled by fast = x + n * c + c - y
Distance traveled slow = x + c - y
We have the equation 2 * (x + c - y) = x + n * c + c - y
Solve for x = (n - 1) * c + y
That is to say, no matter how many circles fast walks from the encounter point, as long as he walks through y, he must return to the entry point. When n = 1, x = y
Conclusion: x = y So we have an idea:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                fast = head;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }
}

5. 🥇 Intersecting linked list

Question link: Intersecting linked list

At first glance this topic is a bit strange, traversal? Is the node pointed to at the same time the desired node? same length? Obviously the lengths are different, so find the lengths one by one? I just don't want to, what should I do? At this time, we see that the linked list of the title description needs to keep the original structure. I don't think so. If it's a big deal, change it and then change it back. At this time, we have an idea to turn any linked list into a A ring, and then back to the problem of finding the ring point of the ring linked list we just talked about😎😎😎

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA == null || headB == null){
            return null;
        }
        ListNode last = headB;
        while (last.next != null){
            last = last.next;
        }
        last.next = headB;

        ListNode fast = headA;
        ListNode slow = headA;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                fast = headA;
                while (fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                last.next = null;//restore empty
                return slow;
            }
        }
        last.next = null;//restore empty
        return null;
    }
}

What I want to say to everyone

Families, after learning this, we unknowingly refreshed 5 linked list OJ questions🥳🥳🥳, and we will continue to update the relevant content of the explosion-proof series in the next new session, learning is never-ending, technology house, save the world!