This is the 4th day of my participation in Gwen Challenge

2021-06-04 LeetCode problem of the Day

Link: leetcode-cn.com/problems/in…

Tags: linked lists

The title

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Enter: intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: Intersected at'8'Interpretation: The value of the intersection node is8(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [4.1.8.4.5], linked list B is [5.0.1.8.4.5]. In A, we have theta before the intersecting node2A node; In B, we have theta before the intersecting node3A node.Copy the code

Enter: intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Intersected at'2'Interpretation: The value of the intersection node is2(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [0.9.1.2.4], linked list B is [3.2.4]. In A, we have theta before the intersecting node3A node; In B, we have theta before the intersecting node1A node.Copy the code

Enter: intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output:nullFrom the respective table headers, linked list A is [2.6.4], linked list B is [1.5]. Because the two linked lists do not intersect, intersectVal must be0, and skipA and skipB can be arbitrary values. The two lists do not intersect, so returnnull 。
Copy the code
The number of nodes in listA is m. The number of nodes in listB is N0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0<= skipB <= n If listA and listB do not intersect, intersectVal is0If listA intersects with listB, intersectVal == listA[skipA +1] == listB[skipB + 1]
Copy the code

Advanced: Can you design a solution with O(n) time complexity and only O(1) memory?

parsing

They ask you to design an answer O(n) in time and O(1) in space. The general idea is to have a two-layer loop, but a closer look at the two lists shows that there is actually a method: Two lists A and B go together, and when A gets to the end, it points back to the head of B, and then A and B go on, and when B gets to the end, it points back to the head of A, so that the two lists are actually the same distance from the end of the list. In this case, we only need two linked lists to walk together, check whether there are equal nodes, return, no two will walk at the end of the same point, pointing to null.

I can think of this idea because I remember where I saw this problem before, and I still have some impression in my mind, otherwise I feel that this method is not very good. It took me 10 minutes to figure out how to write it elegantly and 20 minutes to figure it out.

coding

Inelegant: a count is used to prevent an endless loop when there is no intersection

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode root1 = headA, root2 = headB;
        int count = 0;
        while(root1 ! =null&& root2 ! =null&& root1 ! = root2) { root1 = root1.next; root2 = root2.next;if (root1 == null && count < 2) {
                root1 = headB;
                count++;
            }

            if (root2 == null && count < 2) { root2 = headA; count++; }}returnroot1; }}Copy the code

Gracefully written:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode root1 = headA, root2 = headB;
        while(root1 ! = root2) {if (root1 == null) {
                root1 = headB;
            } else {
                root1 = root1.next; 
            }

            if (root2 == null) {
                root2 = headA;
            } else{ root2 = root2.next; }}returnroot1; }}Copy the code

It could be more elegant:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode root1 = headA, root2 = headB;
        while(root1 ! = root2) { root1 = root1 ==null ? headB : root1.next;
            root2 = root2 == null ? headA : root2.next;
        }   

        returnroot1; }}Copy the code

There’s a lot of time difference between how you write it, so know how to write it, and learn how to write it more elegantly and more comfortably.