力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题

简介: 力扣环形链表(1)进阶环形链表(2)及环形链表的约瑟夫问题

为了加深对环形链表的理解和掌握,这两道题是很不错的选择。

这里所说环形链表不是一个圈圈的结构,而是带环链表。

链接:环形链表(1)

注意这里链表的长度

所以要注意链表是否为空

第一种方法,应该是比较容易想到的方法(偷鸡取脚)

 遍历链表,将每个节点的val更改为一个不容易想到的值,如666666,当遇到一个666666时就返回true,如果在遍历过程中一直走到空都再没有遇到一个666666,那就返回false。

代码如下

bool hasCycle(struct ListNode *head) {
    struct ListNode*p=head;
    while(p){
        if(p->val!=666666)
        {
            p->val=666666;
            p=p->next;
        }
        else 
        return true;
    }
    return false;
}

这种方法明显是投机取巧,所以还有可能被抓到。

运行后还是也可以通过

双指针法(正经方法)

 就想操场的跑道上,有跑的快的人和跑得慢的人,快的人会不断追上慢的人。

 设置双指针,从head开始走,快指针一次跑两步,慢指针一次跑一步,链表中是有环的,快指针一定会抓到慢指针。

 在慢指针进环时,快指针已经在环状里转圈圈了,慢指针一次走一步,快指针一次走两步,慢指针走半圈,快指针就走一圈。

代码如下

bool hasCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

一直找找找,如果有环一定会相遇。

思考:

如果快指针一次走3步,还可以保证能抓到慢指针吗?

 假使慢指针进环时,快慢指针差距m个位置,每次快指针与慢指针的距离差距减小为2,有两种情况。

  1. m为偶数

每次距离都减小2

m-2

m-4

m-6

4

2

0

最终快指针会遇到慢指针。

2. m为奇数

m-2

m-4

3

1

-1

当相差为-1时,快慢指针间的距离变为了m-1。

假设C是环的长度,这里的-1即为C-1;如果环的长度为偶数,那么快慢指针最近的距离为1,因为一次减小的距离为2,所以永远也追不上慢指针。


环形链表(2)

和第一道题不一样的是这道题如果有环,就返回入环的第一个节点,如果链表无环,就返回NULL。

接下来就要进行分析

 当快指针与慢指针相遇时,快指针所走的路程是慢指针的两倍。

 假设起点到入环口的距离是L,圆环的长度为C,入口点到相遇点的距离为x,这时通过分析就可以列出一个等式。

快指针的路程是慢指针的二倍

2(L+X)=L+n( C )+X

可得

L+X=n( C )

L=n( C )-X;

设置两个指针,第一个指针从起始位置出发,另一个指针从相遇点出发,他们就会在环的入口处相遇。

套用第一道题的思路,快慢指针相遇时找到相遇点,在设置两个指针分别出发,直到相遇,如果没有环的话就返回NULL;

代码如下

struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            struct ListNode*meet=slow;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
    }
    return NULL; }

提交后顺利通过。

环形链表的约瑟夫问题

链接:

环形链表的约瑟夫问题

要使用单向链表实现。

 分析题目,构建一个链表,依次储存节点的位置,然后找到链表的尾,尾的next等于头节点,这样一个环形链表就构建成功了。

 从第一个节点开始往后走m-1步(数数时为m,因为第一个节点数1,所以往后走m-1到达目标节点),保存这个节点的next,将起始位置更改为该next,然后从新的起始位置继续往后边数,直到删除到只剩最后一个节点为止,假设这个节点为hei,那么循环结束的条件就是hei->next==hei,判断条件就是hei->next!-hei。

要注意

看代码,讲解很详细

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct ListNode
{
  int val;
  struct ListNode* next;
}LN;
LN* Initnode()
{
  LN* head = (LN*)malloc(sizeof(LN));
  head->next = NULL;
  head->val = 0;
  return head;
}
LN* GetNewnode(int x)
{
  LN* newnode = (LN*)malloc(sizeof(LN));
  newnode->next = NULL;
  newnode->val = x;
  return newnode;
}
void Pushnode(LN* head, int x)
{
  assert(head);
  LN* pre = head;
  while (pre->next)
  {
    pre = pre->next;
  }
  pre->next = GetNewnode(x);
}
void Popnode(LN*head,LN* node)
{
  LN* cur = head;
  while (cur->next != node)
  {
    cur = cur->next;找到要删除的节点的前一个
  }
  LN* next = node->next;
  cur->next = next;
  free(node);
  node = NULL;
}
int main()
{
  int m, n;
  scanf("%d %d", &m, &n);
  //建立链表
  LN* head = GetNewnode(1);//第一个编号为1
  for (int i = 2; i <= m; i++)
  {
    Pushnode(head, i);//建立链表
  }
  //找尾
  LN* cur = head;
  while (cur->next != NULL)
  {
    cur = cur->next;
  }
  cur->next = head;
  //环形链表弄完
  //数数删位
  LN* hei = head;
  while (hei->next != hei)
  {
    for (int i = 1; i < n; i++)//因为移动三步,是移动量两次。
    {
      hei = hei->next;
    }
    LN* pop = hei;//找到要删除的节点pop
    hei = hei->next;//更换hei的位置
    Popnode(hei,pop);//删除pop。
  }
  printf("%d ", hei->val);//打印留下的节点的数值。
  return 0;
}

本文的讲解到这里就结束啦,鄙人才识短浅,如有错误还请多多指教。

目录
相关文章
|
16天前
链表9(优化版)7-9 sdut-C语言实验-约瑟夫问题
链表9(优化版)7-9 sdut-C语言实验-约瑟夫问题
8 0
|
16天前
SDUT 链表9-------7-9 sdut-C语言实验-约瑟夫问题
SDUT 链表9-------7-9 sdut-C语言实验-约瑟夫问题
7 0
|
1天前
【数据结构OJ题】环形链表
力扣题目——环形链表
12 3
【数据结构OJ题】环形链表
|
1天前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
9 1
【数据结构OJ题】环形链表II
|
19天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
19天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
19天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
19天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表