力扣算题【第二期】

简介: 这是一个关于链表操作的算法总结,包括两个部分:1) 反转链表,通过头插法实现链表反转,代码中使用了迭代方式;2) 判断回文链表,利用快慢指针找到链表中点,翻转后半部分并与前半部分比较。代码中包含详细步骤及辅助的翻转函数。

@[toc]

1.反转链表

1.1 算法题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
image.png

1.2 算法思路

1.设置工作指针p,来遍历链表。
2.采用头插法的方法来实现链表翻转。

1.3 代码实现
class Solution {
   
   
    public ListNode reverseList(ListNode head) {
   
   
     ListNode p,q;
     p=head.next;
     head.next=null;
     while(p!=null){
   
   
         q=p.next;
         p.next=head.next;
         head.next=p;
         p=q;
     }
     return head;
    }
}

2.回文链表

2.1 算法题目

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

2.2 算法思路

1.设置快慢指针,当快指针到达链表的末尾时,慢指针正好在链表的中间后者下一个位置。
2.通过翻转链表使得slow指针指向翻转后链表的第一个元素。同时将fast指针也指向当前链表的第一个指针。
3.通过循环判断slow指针和fast指针指向的值是否相同。

2.3 代码实现
class Solution {
   
   
    public boolean isPalindrome(ListNode head) {
   
   
     ListNode fast=head,slow=head;
     while(fast!=null&&fast.next!=null){
   
   
         fast=fast.next.next;
         slow=slow.next;
     }
     if(fast!=null){
   
     //奇数链表
       slow=slow.next;
     }
     fast=head;
     slow=reverse(slow);
     while(slow!=null){
   
   
         if(fast.val!=slow.val){
   
   
             return false;
         }
         fast=fast.next;
         slow=slow.next;
     }
     return true;
    }

    //翻转链表
    public ListNode reverse(ListNode head){
   
   
        ListNode pre=null;
        while(head!=null){
   
   
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}
目录
相关文章
|
5天前
刷爆leetcode第二期
刷爆leetcode第二期
4 0
|
23天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
22 1
|
11月前
|
算法
LeetCode 周赛(2023/07/08)渐入佳境
- 往期回顾:[LeetCode 单周赛第 351 场 · 一场关于子数组的专题周赛](https://mp.weixin.qq.com/s/0KIaUMEpLZw6poHs3cc7MA)
96 0
|
1月前
|
存储 算法 程序员
【Zilliz专场】力扣第 271 场周赛复盘
【Zilliz专场】力扣第 271 场周赛复盘
|
9月前
力扣60天打卡(第四天)
力扣60天打卡(第四天)
LeetCode——新手村
LeetCode——新手村
95 0
|
存储 算法 Java
leetcode每日一题:数组专练篇第二期(2/2)
leetcode每日一题:数组专练篇第二期(2/2)
|
测试技术 API
力扣刷题之路
力扣刷题之路
|
机器学习/深度学习 人工智能 算法
LeetCode 双周赛 99,纯纯送分场!
昨晚是 LeetCode 第 99 场双周赛,你参加了吗?这场周赛整体难度很低,第 4 题评论区普遍认为是 1 字头,纯纯手速场。
110 0