两个链表的第一个公共结点
题目
输入两个链表,找出它们的第一个公共结点。
思路
两个链表有重合,拓扑形状像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; } };