两个链表的第一个公共结点

两个链表的第一个公共结点

题目

  输入两个链表,找出它们的第一个公共结点。

思路

  两个链表有重合,拓扑形状像Y,两个链表有公共结点,那么公共结点出现在链表的尾部,那么从两个链表的最后一个节点开始比较,那么最后一个相同的结点就是我们要找的结点。单链表的最后一个结点,但要最先比较,后进先出,栈!栈!栈!

  1.分别把两个链表放到栈里,尾结点位于栈顶,比较两个栈顶元素是否相同,相同出栈,直到最后一个相同的结点。(当要到达两个链表的尾结点,但是链表的长度不相同,如果从头开始遍历,到达尾结点的时间就不一致。)

  2.先求两个链表的长度,比较他们相差多少结点,再遍历的时候,让长的比短的先走相差的步数,然后再共同向前走,第一个相同的节点就是他们的公共结点。

  3.长短链表指针共同走,短的走的快,比长的先到达链表尾部,当长的到达链表尾部时,短的比长的多走个长度差

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) {
            return NULL;
        }

        ListNode *head_a = headA;
        ListNode *head_b = headB;
        while (head_a != head_b) {
            head_a = head_a == NULL ? headB : head_a->next;
            head_b = head_b == NULL ? headA : head_b->next;
        }
        return head_a;
    }
};

 

上一篇:LeetCode——剑指 Offer两个链表的第一个公共节点


下一篇:你好,谈谈你对前端路由的理解