每日一题:相交链表(LeetCode 160)

题目

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构

解答

以下为双指针解法:

/**
 * 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 *pointA = headA;
        ListNode *pointB = headB;

        //指针 pointA 和 指针 pointB 不断向后遍历,直到找到相交点
        // 不用担心会跳不出这个循环,实际上在链表 headA 长度和链表 headB 长度的之和减一
        // pointA 和 pointB 都会同时指向 null
        while(pointA != pointB)
        {
            pointA  = pointA == NULL? headB : pointA->next;
            pointB = pointB == NULL ? headA : pointB->next;
        }

        return pointA;
    }
};
THE END
分享
二维码
打赏
海报
每日一题:相交链表(LeetCode 160)
题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节……
<<上一篇
下一篇>>