问题：已知两个单链表，它们公共部分，编程找出它们的第一个公共结点。

原理：

解决这个问题的一个直接的思路是遍历。对于第一个链表L1，每遍历一个结点，在第二个链表L2中从头到尾查找是否存在相等（is）的结点。这种方法的时间复杂度为O(mn)。并不是一种好的算法，这里不实现这种算法。

由于两个单链表有公共部分，不难理解，它们的结构是Y型的，如果是X型，那么不符合题设。由于是Y型的，那么在第一个公共结点之后（包括该结点）两链表时重合的。

因此，找出第一个公共结点就相当于逆着两链表（从两链表的公共部分的最后一个结点开始），找到最后一个公共结点，该结点就是我们需要找的结点。

由于链表本事是单链，那么该如何逆着链表呢？很明显，栈提供FILO功能，用它帮助我们解决逆着链表的操作。

利用两个栈，给个栈分别保存链表，然后分别相继弹出元素，那么最后一个相等的元素就是第一个公共结点（明显吧？）

实现：

先实现一个满足功能需求栈，用于保存结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Stack:

    def __init__(self):
        self._s = []

    def empty(self):
        return len(self._s) == 0

    def push(self, item):
        self._s.append(item)

    def pop(self):
        return self._s.pop()

实现部分重合的单链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Node:
    def __init__(self, value):
        self.value = value
        self._next = None

    def __repr__(self):
        return 'Node<{}>'.format(self.value)

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)
node7 = Node(7)

node6._next = node7
node3._next = node6
node2._next = node3
node1._next = node2
node4._next = node5
node5._next = node6

L1 = node1
L2 = node4

可以看出，两链表的公共部分结点值分别是6、7。6就是第一个公共结点值。

L1、L2分别是两链表的头结点。

找出第一个公共结点的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
L1_Stack = Stack()
L2_Stack = Stack()

while L1._next:
    L1_Stack.push(L1)
    L1 = L1._next
L1_Stack.push(L1) # 最后一个结点

while L2._next:
    L2_Stack.push(L2)
    L2 = L2._next
L2_Stack.push(L2) # 最后一个结点

last = None
while not L1_Stack.empty() and not L2_Stack.empty():
    e1 = L1_Stack.pop()
    e2 = L2_Stack.pop()
    if e1 == e2:
        last = e1
    if e1 != e2:
        print("result is ", last)
        print("value is ", last.value)
        break

运行代码后输入结果为6。

现在为上述的思路封装为一个函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Stack:

    def __init__(self):
        self._s = []

    def empty(self):
        return len(self._s) == 0

    def push(self, item):
        self._s.append(item)

    def pop(self):
        return self._s.pop()

def find_first_common_node(L1, L2):

    L1_Stack = Stack()
    L2_Stack = Stack()
    
    while L1._next:
        L1_Stack.push(L1)
        L1 = L1._next
    L1_Stack.push(L1) # 最后一个结点
    
    while L2._next:
        L2_Stack.push(L2)
        L2 = L2._next
    L2_Stack.push(L2) # 最后一个结点
    
    last = None
    while not L1_Stack.empty() and not L2_Stack.empty():
        e1 = L1_Stack.pop()
        e2 = L2_Stack.pop()
        if e1 == e2:
            last = e1
        if e1 != e2:
            return last

上述问题的完整代码见github。