作文以记之 ~ 相交链表

作文以记之 ~ 相交链表

• 0、前言
• 1、题目描述
• 2、解题思路
• • 2.1 方法1 ~ 简单利用双指针
  • • 2.1.1 思路
    • 2.1.2 程序代码
  • 2.2 方法2 ~ 利用双指针
  • • 2.2.1 思路
    • 2.2.2 程序代码
  • 2.3 其他方法

0、前言

此篇博客是力扣上 160. 相交链表 题目的题解，题目不难，写这篇博客是为了记录一下官方题解中给出的精彩答案！github 相关链接可 点击此处 进行查看！

1、题目描述

2、解题思路 2.1 方法1 ~ 简单利用双指针 2.1.1 思路

解决这个题采用了一个取巧的方式，即先求出两个链表各自的长度lenA、lenB，再以最短的链长为基准，将较长链表的节点遍历至其自身第（max(lenA,lenB)-min(lenA,LenB)）个节点。

此时，该链表与另一链表同时开始遍历，找寻相同节点！

2.1.2 程序代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int ComputeLen(ListNode* head)
    {
        int len = 0;
        while(head)
        {
            len++;
            head=head->next;
        }
        return len;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = ComputeLen(headA);
        int lenB = ComputeLen(headB);
        ListNode* nextA = headA;
        ListNode* nextB = headB;
        if(lenA > lenB)
        {
            int tmp = lenA-lenB;
            while(tmp)
            {
                nextA = nextA->next;
                tmp--;
            }
        }
        else
        {
            int tmp = lenB-lenA;
            while(tmp)
            {
                nextB = nextB->next;
                tmp--;
            }
        }
        int mid = min(lenA,lenB);
        while(mid)
        {
            if(nextA == nextB)
                return nextA;
            nextA=nextA->next;
            nextB=nextB->next;
            mid--;
        }
        return NULL;
    }
};

2.2 方法2 ~ 利用双指针 2.2.1 思路

注：此处思路来源于官方题解中的一个思路，具体可 点击此处 进行查看！

2.2.2 程序代码

/**
 * 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==nullptr||headB==nullptr) return NULL;
        ListNode* s1 = headA,*s2=headB;
        while(s1 != s2)
        {
            s1 = s1 == nullptr? headB:s1->next;
            s2 = s2 == nullptr? headA:s2->next;
        }
        return s1;
    }
};

2.3 其他方法

关于该题还有其他方法，比如哈希表，但觉得太简单了，此处就不配代码了。

后面若有其他想法，再补充吧！

侵权删~