1 问题
输入两个链表，如何可以快速找出它们的第一个公共结点？
2 方法
两个有共同节点的链表是Y型结构，也就是自第一个公共节点开始，都是重合的。问题要求，要找到第一个公共节点，可以反其道而行之，从后往前找，如果是重合节点，这两个节点一定是相等的，所以最后一个相等的节点就是第一个公共的节点。具体方法可以先将每个链表中的节点循环添加到栈中，然后从栈中弹出，一一比较即可。
代码清单 1
class ListNode(self, x): self.val = x self.next = None class Solution: def findCommonNode(self, pHead1, pHead2): #首先判断是否为空 if not pHead1 or not pHead2: return None #两个辅助栈，将数据添加进去 stack1 = [] stack2 = [] while pHead1: stack1.append(pHead1) pHead1 = pHead1.next while pHead2: stack2.append(pHead2) pHead2 = pHead2.next #定义要输出的变量，开始比较栈的值是否一样 res = None while stack1 and stack2: p1 = stack1.pop() p2 = stack2.pop() if p1.val == p2.val: res = p1 else: break return res l1 = ListNode(1) l1.next = ListNode(5) l1.next.next = ListNode(7) l1.next.next.next = ListNode(9) l2 = ListNode(2) l2.next = ListNode(3) l2.next.next = ListNode(4) l2.next.next.next = ListNode(5) l2.next.next.next.next = ListNode(7) l2.next.next.next.next.next = ListNode(9) test = Solution() test.findCommonNode(l1,l2).val |
|---|
3 结语
此方法主要是比较两个链表里面的字是相同的即可，可以从后往前找，利用栈先进后出，后进先出的特点，弹出的值最后一个相等的节点就是第一个公共的节点。第二种方法是比较两个链表的长度，让长的先走|l1-l2|步，两个链表同在一起跑线上，第一相等的就是第一个公共点。此方法还不够完善在以后可以再继续改进和改善，以此来寻求更好的代码解决此类问题。
