Appetizing:

There are two linked lists: L1 and L2; L1: 1->2->3->4, L2: 1->2->3->5

  • Q: Are L1 and L2 equal? (Use “==” and “equals” to judge)

The specific code is as follows:

private static boolean test1() { ListNode l1 = new ListNode(1); l1.next = new ListNode(2); l1.next.next = new ListNode(3); L1.next-next-next. Next = new ListNode(4); ListNode l2 = new ListNode(1); l2.next = new ListNode(2); l2.next.next = new ListNode(3); L2.next-next-next. Next = new ListNode(5); if (l1==l2) { return true; } return false; }Copy the code

Off-the-cuff answers:

As a Java programmer, you don’t need to clap your thighs to answer this question: No matter what you use “==” or “equal” to operate it, it always return a “false” for you!

Enter the scene, then detail:

  • Let’s walk into Leetcode’s circular linked list 2

There is a line slow == fast that is the core of the business. Without this line, the code will run out of time.

Source of slow == fast:

Look at the whole, look at the parts, tasteless

public ListNode detectCycle(ListNode head) {
        // Boundary conditions
        if (head == null) {
            return null;
        }
        // The speed pointer
        ListNode fast = head;
        ListNode slow = head;
        // In each loop, the fast pointer runs one more step than the slow one. In the body of the loop, there is a phenomenon that the fast pointer is chasing the slow pointer
        while(fast ! =null&& fast.next ! =null) {
            fast = fast.next.next;
            slow = slow.next;
            // Under what conditions does the "==" operation return true?
            if (slow == fast) {
                // Exit this point, is the encounter point;
                break; }}if (fast == null || fast.next == null) {
            return null;
        }
        
        fast = head;
        while(slow ! = fast) { fast = fast.next; slow = slow.next; }return slow;
    }

Copy the code

The debug it:

  • Key codes key analysis:
// Under what conditions does the "==" operation return true?
if (slow == fast) {
   // Exit this point, is the encounter point;
   break;
 }
Copy the code
  • Copy from leetcode

  • The result of the creation (aside from stackOverFlow exceptions, is there a loop?)

  • Remember, at the very beginning, the fast pointer and slow are equal!

Note: When fast and slow are fast, they are not equal;

  • Fast starts chasing slow until it’s equal! Main: We want to know the equality, at last can see;

  • Take another look at Hash

Now, is it suddenly enlightened? Did you create L1 and L2, or did you take a screenshot from the same list Head? To determine equality, you essentially use HashCode;

Wrong idea:

  • As shown in the figure above, the linked list: L1 and L2, the current node is 1.
  • At first, I thought it was equal, because the nodes were all 1. “==” excludes L1’s 2,4 nodes, and L2’s 2,5 nodes. But the brush brush, always feel wrong, I think of exclusion, does not violate the idea of OOP encapsulation? Node 2 is the next attribute of node 1, node 4 is the attribute of node 2, node L2;
  • So: L1 == L2 is not judged by current node (i.e. 1 node), but by the hashcode of the whole linked list. (overall view) That is the truth etc….

Think about:

  • It’s really important to know the ins and outs of each line of code when you’re doing this.
  • Brush, really useful;