題目描述 輸入兩個鏈表，找出它們的第一個公共結(jié)點(diǎn)。
題目解析 如果兩個鏈表有公共結(jié)點(diǎn)，那么兩個鏈表公共結(jié)點(diǎn)之后的結(jié)點(diǎn)也都相同，那么兩個鏈表交叉后一定是一個Y型，所以如果我們將兩個鏈表放到兩個棧里邊，當(dāng)我們從棧里邊同時出棧兩個鏈表的結(jié)點(diǎn)，直到最后一個相同的結(jié)點(diǎn)，這是算法1。對于兩個不同的鏈表，有公共結(jié)點(diǎn)的話，那么如果我們先遍歷一個較長的鏈表，讓兩個鏈表剩下的結(jié)點(diǎn)個數(shù)相同，那么我們只需要同時遍歷兩個鏈表，直到第一個相同的結(jié)點(diǎn)。
代碼如下：
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null || pHead2 == null) { return null; } Stack<ListNode> stack1 = new Stack<>(); Stack<ListNode> stack2 = new Stack<>(); ListNode temp = pHead1; while (temp != null) { stack1.push(temp); temp = temp.next; } temp = pHead2; while (temp != null) { stack2.push(temp); temp = temp.next; } temp = null; ListNode node1 = null; ListNode node2 = null; while (stack1.size() > 0 && stack2.size() > 0){ node1 = stack1.pop(); node2 = stack2.pop(); if (node1.val == node2.val && node1.next == node2.next){ temp = node1; }else{ break; } } return temp; } public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) { if (pHead1 == null||pHead2 == null) { return null; } int count1 = 0; ListNode p1 = pHead1; while (p1!=null){ p1 = p1.next; count1++; } int count2 = 0; ListNode p2 = pHead2; while (p2!=null){ p2 = p2.next; count2++; } int flag = count1 - count2; if (flag > 0){ while (flag>0){ pHead1 = pHead1.next; flag --; } while (pHead1!=pHead2){ pHead1 = pHead1.next; pHead2 = pHead2.next; } return pHead1; } if (flag <= 0){ while (flag<0){ pHead2 = pHead2.next; flag ++; } while (pHead1 != pHead2){ pHead2 = pHead2.next; pHead1 = pHead1.next; } return pHead1; } return null; }新聞熱點(diǎn)
疑難解答
