【链表OJ】相交链表 环形链表1

前言:

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上链表OJ题目

一.leetcode 160. 相交链表

来源:160. 相交链表 - 力扣（LeetCode）

1.问题描述:

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回NULL 。

图示两个链表在节点c1开始相交：

已知a1与b1的头结点地址，并分别用headA和headB指针指向

• 题目数据 保证 整个链式结构中不存在环。
• 注意，函数返回结果后，链表必须 保持其原始结构 。

题目接口:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
}

2.解题思路:

原始链表：

• 首先定义tailA和tailB分别遍历a链表和b链表,在遍历过程中，分别求出两链表长度,分别定义为lenA和lenB,然后用lenA和lenB相减取差的绝对值，计为差距步gap

然后定义指向长链表的指针longList,和指向短链表的指针shortList，用前面定义的LenA和LenB比较它们的长度,进行合适赋值，接着让长的链表走差距步gap。若长链表结点的地址不等于短链表，则让tailA和tailB指针继续走，有相等结点则跳出循环，返回此时的longList或者shortList。

实现代码:

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
  struct ListNode* tailA = headA;
  struct ListNode* tailB = headB;
  int lenA = 1, lenB = 1;//原始长度定义为1才是正确的
    while (tailA)
    {
      tailA = tailA->next;
      lenA++;
    }
    while (tailB)
    {
      tailB = tailB->next;
      lenB++;
    }
    if (tailA != tailB)//若两指针到结束也找不到相等结点，则返回NULL
      return NULL;
    int gap = abs(lenA - lenB);//取出两者相减的绝对值，赋值给gap表示两链表的差距步
    struct ListNode*longList = headA;//先假定A链表为长链表
    struct ListNode* shortList = headB;
    if (lenA < lenB)//接着两链表比较，如果满足此条件，则重新赋值，定义B链表的为长链表
    {
      longList = headB;
      shortList = headA;
    }
  while (gap--)//长链表先走差距步
  {
    longList = longList->next;
  }
  while (longList != shortList)//若没有相等(地址相等)则继续遍历
  {
    longList = longList->next;
    shortList = shortList->next;
  }
  return shortList;
}

代码执行:

二.leetcode 141.环形链表

1.问题描述:

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true。 否则，返回 false。

题解接口:

bool hasCycle(struct ListNode *head) {
}

2.代码思路:

本题的代码思路:

定义一个快指针,让其先走两步,接着定义一个慢指针，一次走一步，反复此循环。

• 如果快慢指针指向的地址相等，则证明链表中存在环。
• 如果快指针提前指向NULL，循环结束，则证明不是环形链表，直接返回false。

函数实现

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow =head;
    while(fast && fast->next)
   {
     fast=fast->next->next;//快指针先走两步,慢指针走一步
     slow=slow->next; //慢指针走一步
    if(fast==slow)//指针相遇表明链表带环
    {
        return true;
    }
    }
    return false;//否则返回NULL
}

代码执行:

然而本题的重点在于如何证明上面的代码的实现逻辑，是一个数学问题。

3.问题证明:

1、slow和fast一定会相遇吗?

答:一定会

画一张图来证明一下, 此时两指针同时指向头节点的地址。

接着先让快指针fast=fast->next->next(快指针先走两步),后让 slow=slow->next(慢指针走一步).

fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N

slow进环以后，fast开始追击slow,slow每走1步，fast每走2步，他们之间距离缩小1。

2、slow走1步，fast走n(3/4/5….)步可以吗?(n > 2)

不一定

举例:

slow每次走一步，fast每次走三步，它们一定可以相遇吗？答:不一定。

画图

当快慢指针之间的距离个数为奇数时

fast会先进环，slow会后进环，假设slow进环时， slow和fast之间的距离为N

slow进环以后，fast开始追击slow，slow每走1步，fast每走3步，他们之间距离缩小2

当快指针追赶上慢指针时,此时错过了,并进入新一轮的追击,假设一个值C为环的长度,那么快慢指针的距离此时必为C-1

所以,如果C-1是奇数那么fast永远追不上slow

当C-1的距离为偶数时,那么此时的距离变化为

N N-2 N-4 ... 4 2 0 ，0则表示此时两指针相遇，表明下一轮可以追上。

     本文结束，如有错误，我会继续更新关于链表oj的题目，欢迎大家指正!