【脚指 offer 24、25】 反转链表 + 合并两个排序的链表

简介: 【脚指 offer 24、25】 反转链表 + 合并两个排序的链表

前言

数据结构与算法属于开发人员的内功,不管前端技术怎么变,框架怎么更新,版本怎么迭代,它终究是不变的内容。 始终记得在参加字节青训营的时候,月影老师说过的一句话,不要问前端学不学算法。计算机学科的每一位都有必要了解算法### ,有写出高质量代码的潜意识

一、反转链表

1.1 问题描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1.2 问题分析

利用两个变量来记录节点;

  • cur 记录正序遍历的当前节点;
  • prev 当前节点的上一个节点,初始值为null 进行正向迭代,每次将当前节点指向上一个节点,利用临时变量temp来记录下一个节点。

1.3 AC代码

var reverseList = function(head) {
    let prev = null
    let cur = head
    while(cur){
        const temp = cur.next
        cur.next = prev
        prev = cur
        cur = temp
    }
    return prev
};

二、 合并两个排序的链表

2.1 问题描述

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

2.2 问题分析

先创建一个结果链表,迭代比较两个链表的值,小的插入到结果链表中,指针往后挪一位。

2.3 AC代码

ar mergeTwoLists = function(l1, l2) {
    let dommy = new ListNode(-1)
    let p = dommy 
    while(l1||l2){
        if(l1&&l2){
            if(l1.val<l2.val){
                p.next = new ListNode(l1.val)
                l1 = l1.next
                p = p.next
                continue
            }else{
                p.next = new ListNode(l2.val)
                l2 = l2.next
                p = p.next
                continue
            }
        }else if(l1){
            p.next = new ListNode(l1.val)
            l1 = l1.next
            p = p.next
            continue
        }else{
            p.next = new ListNode(l2.val)
            l2 = l2.next
            p = p.next
            continue
        }
    }
    return dommy.next
};

image.png

总结

好了,本篇脚趾offer 用两个栈实现队列到这里就结束了,我是邵小白,一个在前端领域摸爬滚打的大三学生,欢迎👍评论。

相关文章
|
6月前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
46 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
22天前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
40 0
|
26天前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
29 0
|
3月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
3月前
|
存储 算法 Java
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题:反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
42 0
|
5月前
|
存储 人工智能 测试技术
每日练习之排序——链表的合并;完全背包—— 兑换零钱
每日练习之排序——链表的合并;完全背包—— 兑换零钱
31 2
|
6月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
50 1
|
6月前
23. 合并 K 个升序链表
23. 合并 K 个升序链表
54 3
|
5月前
23.合并K个升序链表
23.合并K个升序链表
|
5月前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】