20200926.md

Algorithm

剑指offer-两个链表的第一个公共节点

Description

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

Solution

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        if (node1 == null || node2 == null) {
            return null;
        }
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);
        if (length1 >= length2) {
            int len = length1 - length2;
            while (len > 0) {
                node1 = node1.next;
                len--;
            }
        } else if (length1 < length2) {
            int len = length2 - length1;
            while (len > 0) {
                node2 = node2.next;
                len--;
            }
        }
        while (node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    private int getLength(ListNode pHead) {
        int length = 0;
        ListNode current = pHead;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }
}

Discuss

1. 两连表的长度差

2. 如果链表1的长度大于链表2的长度

3. 先遍历链表1，遍历的长度就是两链表的长度差

4. 如果链表2的长度大于链表1的长度

5. 先遍历链表1，遍历的长度就是两链表的长度差

6. 开始齐头并进，直到找到第一个公共结点

其他思路：

如果存在共同节点的话，那么从该节点，两个链表之后的元素都是相同的。 也就是说两个链表从尾部往前到某个点，节点都是一样的。 我们可以用两个栈分别来装这两条链表。一个一个比较出来的值。 找到第一个相同的节点。

Review

Tip

Share