【力扣刷题】回文链表、环形链表、合并两个有序链表

简介: 【力扣刷题】回文链表、环形链表、合并两个有序链表

、回文链表

1.1 题目描述

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。




1.2 思路分析

首先是要对该链表进行非空校验,若是空链表,直接返回fasle,否则,执行其它逻辑,按照回文链表的规律,可以有这样一个思路:若它是回文链表,可先找到他的前半个回文链表的最后一个节点,通过这个节点,就能找到开始回文的下半个链表的最后一个节点,从该节点处,将后半个回文链表进行整体反转,然后再定义指针进行遍历,从前半个回文链表的头开始作为p1指针,后半个回文链表的头作为p2指针,遍历整个回文链表,判断它们的值是否相同,若不相同,则不是回文链表,否则就是回文链表。

1.3 代码演示

public boolean isPalindrome(ListNode head) {
        //非空判断
        if (head == null) {
            return false;
        }
        //找到回文链表前一段的最后一个节点
        ListNode firstHalfEnd = endOfFirstList(head);
        //找到回文链表反转后的第一个节点
        ListNode firstHaftStart = reverse(firstHalfEnd.next);
        //设置标记
        boolean result = true;
        //设置遍历指针
        ListNode p1 = head;
        ListNode p2 = firstHalfStart;
        while(result && p2 != null) {
            if(p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        //恢复链表
        firstHaftEnd.next = reverse(firstHalfEnd.next);
        return result;
    }
    public static ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
    public static ListNode endOfFirstList(ListNode head) {
        //设置快慢指针进行查找
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

二、环形链表

2.1 题目描述

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

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

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





2.2 思路分析

先进行非空校验,若head为null,字直接返回false,否则进行其它代码,定义快慢指针slow和fast,fast指针比slow指针快走两步,while循环进行遍历,条件是slow不等于fast,遍历整个链表,循环内是快慢指针的执行,当链表存在环时,fast指针总会多转几圈从而追上慢指针slow,此时两个指针均指向同一个节点,表示该链表存在环,跳出循环,返回true,若是在循环中fast指向了空或者fast.next指向了空,表示该链表是正常的单向链表,直接返回false即可。

2.3 代码演示

public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            //fast指针每次比slow指针快走两步
            //若该链表存在环,则这两个指针会进入环中
            //fast总有机会比slow多转n圈从而追上slow
            //此时跳出循环,表示该链表是环形来链表
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

三、合并两个有序链表

3.1 题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。




3.2 思路分析

按照题目要求,可以先对空值进行校验,若两个链表均为空,则直接返回空,若只有一个链表为空,则直接返回另一个链表,否则进行其它代码,定义一个哨兵节点并定义一个指向它的的指针,当两个链表均不为空时,以此为条件开始遍历,在循环中判断两个链表当前的节点值的大小情况,若链表1的值小,则将哨兵位的下一个节点指向链表1,否则,则将哨兵位的下一个节点指向链表2,然后prev指向prev.next继续遍历链表,循环结束时,若链表长度不等,则较长的链表直接将剩余的节点加到prev的next下,返回合并后的链表的头节点,即哨兵位的下一个节点。

3.3 代码演示

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null && list2 == null) {
            return null;
        }
        if(list1 == null && list2 != null) {
            return list2;
        }
        if(list1 != null && list2 == null) {
            return list1;
        }
        //定义一个哨兵位节点
        ListNode preHead = new ListNode(-1);
        //定义一个指针指向哨兵位,作为遍历指针
        ListNode prev = preHead;
        //当链表都不为空时,开始遍历
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {     //遍历链表,比较链表当前节点的值的大小
                prev.next = list1;          //若链表1的值小,则将哨兵位的下一个节点指向链表1
                list1 = list1.next;         //链表1继续遍历
            } else {
                prev.next = list2;          //若链表2的值小,则将哨兵位的下一个节点指向链表2
                list2 = list2.next;         //链表2继续遍历
            }
            prev = prev.next;               //prev继续遍历链表
        }
        prev.next = list1 == null ? list2 : list1;  //若链表长度不等,则较长的链表直接将剩余的节点加到prev的next下即可
        return preHead.next;                        //返回合并后的链表的头节点,即哨兵位的下一个节点
    }


相关文章
|
3天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
9 2
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
6天前
21. 合并两个有序链表
21. 合并两个有序链表
|
7天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
7天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
7天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
10天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
7天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表