LeetCode 160. 相交链表

Michael阿明

发布于 2021-02-20 11:11:11

29200

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 题目信息

编写一个程序，找到两个单链表相交的起始节点。《剑指Offer》同题：面试题52. 两个链表的第一个公共节点《程序员面试金典》同题：面试题 02.07. 链表相交

2. 解题

2.1 计算长度

先算出两根链表a、b的长度，两个指针都位于各自开始处
让长的一根从起点先走abs（a、b长度差）步
然后一起走，相同的时候返回该处指针

/**
 * 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) {
        ListNode *ha = headA, *hb = headB;
        int lena = 0, lenb = 0;
        while(ha)
        {
        	++lena;
        	ha = ha->next;
        }
        while(hb)
        {
        	++lenb;
        	hb = hb->next;
        }
        int t = abs(lena - lenb);
        hb = headB;
		ha = headA;
        if(lenb >= lena)
        {
        	while(t--)
        		hb = hb->next;
        }
        else//(lenb < lena)
        {
        	while(t--)
				ha = ha->next;       	
        }
        while(ha&&(ha!=hb))
    	{
    		ha = ha->next;
    		hb = hb->next;
    	}
    	return ha;
	}
};

2.2 交替遍历

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *ha = headA, *hb = headB;
        while(ha != hb)
        {
            ha = ha? ha->next : headB;//到达尾部，跳转到另一条链表
            hb = hb ? hb->next : headA;
        }
        return ha;
    }
};