《新星计划之链表》环形链表、回文链表(图解分析)

简介: 《新星计划之链表》环形链表、回文链表(图解分析)

环形链表

f6b0f1f1e931493980518e1754734667.png

原题链接:环形链表


分析:对于链表的很多题目我们经常会用到一种思想——双指针,我们这道题目也用到了双指针这一思想,即定义两个对结点的引用变量fast和slow,他们一开始都分别指向头结点。但不同的是fast每次移动两个结点,slow每次移动一个结点。


这样的话如果链表中存在环的话,他们两个一定会相遇,如图所示:


df8f2aeba032770d580827ae7529c7b8.gif

代码如下:

// 环形链表
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, show = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            show = show.next;
            if (fast == show) {
                return true;   // 如果有环的话,他们两个一定能相遇
            }
        }
        return false;
    }
}

但这里有一个小细节,在while的循环条件里fast != null这个判断条件不能丢

为啥呢?如图所示:

c121de0bdf82474dab0c2d8b7a808d45.png

回文链表

69e25fdde6564b7d97a479c42009adb3.png


原题链接回文链表

思路:一开始我想是反转链表后再与原链表比较,但问题是再我们反转链表的过程中原来的链表已经变了。

1057d3e2027a4fed909eb728c5556e6c.png

🍑所以我们不妨换个思路,你看如果一个链表是回文链表的话:它是不是正好分成了两个部分,既然我们不能反转整个链表,那么我们能不能对链表的后半部分进行反转,这样如果反转后的后半部分和前半部分是重合的,那么就说明这是一个回文链表。

🍑那么问题又来了?我们怎样把链表分为两部分呢?就是如上图所示只有我们能够找到链表的中间位置3就好。


我们定义两个结点的引用fast和slow,fast每次移动两个结点,slow每次移动一个结点。

能够移动的条件就是:

 while (fast != null && fast.next != null)

开始时


51ea6ce18ef043c1ad868ef619754ff4.png


结束时


3631f9fa66824e5dbdae9c38c518cc2c.png

 可以发现当fast移动结束后,slow就会移动到中间,那么这样一来移动后的slow所指向的结点就是我们链表的中间结点。


📝总结一下就是:

  1. 1.用快慢指针找到中间位置,把代码分为前后两个部分
  2. 2.对后半部分进行旋转操作
  3. 3.比较前后两个部分是否相等
class Solution {
    // 首先要找到中间结点
    public ListNode midFind(ListNode slow, ListNode fast) {
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;  // 此时慢指针所指向的就是中间结点
    }
    // 反转链表,把中间结点之后的结点进行反转
    public ListNode reverseList(ListNode cur) {
        ListNode pre = null;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
   }
    // 判断前后两部分是否相等
    public boolean isPalindrome(ListNode head) {
        ListNode dummyHead = new ListNode(0, head);  // 设置虚拟头结点,当结点只有较少时方便处理
        ListNode mid = midFind(dummyHead, dummyHead); // mid链表的中间结点
        // 对中间结点往后的后半部分进行反转
        ListNode tail = reverseList(mid.next);
        while(dummyHead != mid && head != null && tail != null) {
            if (head.val != tail.val) {
                return false;
            }
            head = head.next; 
            tail = tail.next;
        }
        return true;
    }
}


相关文章
|
22天前
|
Java
环形数组链表(java)
环形数组链表(java)
11 0
|
6天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
8 0
【数据结构OJ题】链表的回文结构
|
16天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
10 0
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
22天前
|
算法 C语言
【数据结构与算法 经典例题】链表的回文结构(图文详解)
【数据结构与算法 经典例题】链表的回文结构(图文详解)
|
22天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
22天前
|
存储 算法 C语言
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
30 1
|
2月前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
34 1
|
2月前
题目----力扣--回文链表
题目----力扣--回文链表
23 0