習題——倆個連結清單的第一個公共節點

倆個連結清單的第一個公共節點

1.題意描述

• 輸入兩個連結清單，找出它們的第一個公共節點。

2.輸入輸出描述

• 如下圖，公共節點就是8這個節點

  

3.代碼實作

• 第一種方法，用HashSet的不重複性

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //第一種：用HashSet
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //可以選擇set将A全部放進去，然後周遊B，如果有直接傳回節點，最後傳回null；
        Set<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }

        while(headB != null){
            if(set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
}
}
           

• 第二種方法;周遊，如果倆個連結清單長度不一樣，讓長度一樣的先走，等他們倆個長度一緻，一起走，然後相同的節點就是結果

  

在這裡插入代碼片/**
 * 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) {
        //2.讓連結清單長度長的先走，直到他們倆個長度一緻，然後一起走，直達找到一樣的傳回，否則就傳回null；
       int lenA = length(headA); int lenB = length(headB);
        while(lenA != lenB){
            if(lenA > lenB){
                headA = headA.next;
                lenA--;
            }else{
                headB = headB.next;
                lenB--;
            }
        }
        //到了這裡倆者長度一緻，一起走
        while(headA != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;

        }
        return null;
    }
    //統計連結清單的長度
private int length(ListNode node) {
    int length = 0;
    while (node != null) {
        node = node.next;
        length++;
    }
    return length;
}
}
           

• 第三種方法

1. 倆個連結清單同時開始周遊，如果連結清單A走完，然後從B的頭節點開始周遊；
2. 同樣B走完了，從A的頭節點開始周遊；
3. 一直到他們倆個周遊的節點重合就是結果；

   

   

在這裡插入代碼片/**
 * 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) {
    //第三種
    //tempA和tempB我們可以認為是A,B兩個指針
    ListNode tempA = headA;
    ListNode tempB = headB;
    while (tempA != tempB) {
        //如果指針tempA不為空，tempA就往後移一步。
        //如果指針tempA為空，就讓指針tempA指向headB（注意這裡是headB不是tempB）
        tempA = tempA == null ? headB : tempA.next;
        //指針tempB同上
        tempB = tempB == null ? headA : tempB.next;
    }
    //tempA要麼是空，要麼是兩連結清單的交點
    return tempA;
}
}