The first common node of two linked lists

Topic describes

Enter two linked lists to find their first common node.

Idea 1

  • Scan “two linked lists” with two Pointers, and eventually both Pointers reach NULL or the common node. (* * * * *)
Program (Java)
/** * code1 * time complexity: O(), space complexity: O(1) */ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 ! = p2) { p1 = (p1 ! = null ? p1.next : pHead2); p2 = (p2 ! = null ? p2.next : pHead1); }returnp1; } } /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }} * /Copy the code

Idea 2

  • If two lists have common nodes, the common nodes appear at the end of both lists. Use two secondary stacks: place two linked list nodes on each stack so that the end of each list is at the top of each stack, and then compare whether the nodes at the top of each stack are the same. If they are identical, the top of the stack is ejected and the next top is compared until the last identical node is found.
Program (Java)
/** * code2 * time complexity: O(m+n), space complexity: O(1) */ java.util. public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if (pHead1 == null || pHead2 == null) {
            return null;
        }
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
 
        while(pHead1 ! = null) { stack1.push(pHead1); pHead1 = pHead1.next; }while(pHead2 ! = null) { stack2.push(pHead2); pHead2 = pHead2.next; } ListNode commonListNode = null;while(! stack1.isEmpty() && ! stack2.isEmpty() && stack1.peek() == stack2.peek() ) { stack2.pop(); commonListNode = stack1.pop();; }returncommonListNode; }}Copy the code

Idea 3

  • First, the length1 and length2 of two linked lists are traversed to obtain their length. If the length of the linked list is not the same, the length1-length2 step of the longer list is first traversed in the second traversal, and then the first identical node is found on both lists.
Program (Java)
    /** * code3 * time complexity: O(m+n), space complexity: O(1) */
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null||pHead2==null) {return null;
        }
        if(pHead1==pHead2){
            return pHead1;
        }
        int length1=0;
        int length2=0;
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while(p1! =null){
            length1++;
            p1=p1.next;
        }
        while(p2! =null){
            length2++;
            p2=p2.next;
        }
        if(length1-length2<0){
            ListNode temp=pHead2;
            pHead2=pHead1;
            pHead1=temp;
        }
        int count=(length1-length2)>0? (length1-length2):(length2-length1);while(count--! =0){
            pHead1=pHead1.next;
        }
        while(pHead1! =pHead2){ pHead1=pHead1.next; pHead2=pHead2.next;if(pHead1==null||pHead2==null) {return null; }}returnpHead1; }}Copy the code