首页 > 其他分享 >LeetCode24:两两交换链表中的节点

LeetCode24:两两交换链表中的节点

时间:2024-11-02 20:45:57浏览次数:3  
标签:tmp next 链表 n1 LeetCode24 n2 节点

原题地址:. - 力扣(LeetCode)

题目描述

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

解题思路

  • 定义节点:我们使用一个ListNode类表示单链表的节点,包含节点的值和指向下一个节点的指针。

  • 边界条件:首先检查链表的头节点是否为空或只有一个节点。如果是,直接返回头节点,因为没有需要交换的节点。

  • 创建虚拟头节点:使用一个虚拟头节点(dummy)来简化边界情况的处理,特别是处理链表的开头节点。

  • 循环交换节点:使用一个指针tmp遍历链表,直到没有更多的节点可以交换:

    • 获取当前待交换的两个节点(n1n2)。
    • 进行节点交换,将tmp.next指向n2,并调整n1n2next指针。
    • 更新tmp指向n1,为下一个交换做准备。
  • 返回结果:最终返回虚拟头节点的下一个节点,即新的头节点。

源码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 检查链表是否为空或只有一个节点
        if (head == null || head.next == null) {
            return head; // 直接返回原链表
        }

        // 创建一个虚拟头节点,方便操作
        ListNode dummy = new ListNode(0);
        dummy.next = head; // 虚拟节点指向原链表的头
        ListNode tmp = dummy; // 用于遍历的指针

        // 遍历链表,直到没有足够的节点进行交换
        while (tmp.next != null && tmp.next.next != null) {
            ListNode n1 = tmp.next; // 当前节点
            ListNode n2 = tmp.next.next; // 下一个节点

            // 进行节点交换
            tmp.next = n2; // tmp指向n2
            n1.next = n2.next; // n1指向n2的下一个节点
            n2.next = n1; // n2指向n1

            // 更新tmp指针,为下次交换做准备
            tmp = n1; 
        }

        // 返回新的头节点
        return dummy.next; 
    }
}

复杂度分析

  • 时间复杂度:O(n),其中n是链表的节点数。每个节点最多被访问两次,所以整体时间复杂度是线性的。
  • 空间复杂度:O(1)。我们只使用了常数的额外空间,不需要额外的存储结构。因此空间复杂度为常数。

标签:tmp,next,链表,n1,LeetCode24,n2,节点
From: https://blog.csdn.net/qq_36070104/article/details/143456121

相关文章

  • LeetCode25:K个一组翻转链表
    原题地址:.-力扣(LeetCode)题目描述给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值,而是需......
  • 关于k8s api-server端口范围和node节点范围冲突会导致集群不正常故障总结
    1.故障背景由于需要部署新环境,于是在阿里云新建一个ack集群,部署了业务,结果整晚上的存活探针告警,新集群接近30个业务pod,整晚上将近50多条存活探针告警,这个结果明显不正常。但是查看所有pod状态事件全部正常,阿里云托管的ack也没有事件异常,第一反应确实是集群某些参数不对......
  • 代码随想录一刷day6 (链表day2)(链表完结)
    24.两两交换链表中的节点分三步走;1.创建dummyhead2.三个指针 cur  t1 t23.  cur->next=t2;  t1->next=t2->next;  t2->t1->next; 最后让cur=t1;注意最后返回的是dummyhead-》next 而不是head;注意最后deletedummyhead19.删除链表的倒数第N个节点注......
  • shell+expect创建多个节点无密码ssh
    #!/bin/bashpassword="liwanliang"#1.echo"为每个节点创建公密钥对..."fornodeinnode{061..065}doecho"${node}开始操作"expect-c"settimeout1log_user0spawnsshroot@${node}......
  • 【PAT_Python解 AC满分代码】1105 链表合并
    原题链接:PTA|程序设计类实验辅助教学平台Tips:以下Python代码仅个人理解,非最优算法,仅供参考!多学习其他大佬的AC代码!importsysdefmain():#读取链表头和节点数h1,h2,n=map(int,sys.stdin.readline().split())e=[0]*100010#存储数据ne......
  • 代码随想录一刷Day6--链表day1
    1.增加虚拟头节点,使头节点的移除跟别的移除统一(否则头节点需要让head指针往后移)2.删除节点的话,注意delete203.移除链表元素对链表的操作有点不熟悉ListNode*DummyHead=newListNode(0,head);  使用new进行虚拟头节点的创建删除tmp删除分支时,不用让cur=cur-》next 70......
  • C. DS循环链表—约瑟夫环 (Ver. I - B)
    题目描述N个人坐成一个圆环(编号为1-N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。例如:N=3,K=2,S=1。2号先出列,然后是1号,最后剩下的是3号。测试数据有多组,每组包括3个数N、K、S,表示有N个人,从编号为S的人开始,数到K出列。输入测......
  • 链表和数组的插入删除时间复杂度都是o(n),为什么说链表效率高
    链表和数组的插入删除时间复杂度都是o(n),链表效率高的原因:1.动态内存分配;2.插入和删除操作的局部性;3.避免数组的扩容和复制;4.无需移动大量数据;5.适用于频繁的随机插入和删除;6.简化数据结构维护。链表的节点可以在运行时动态分配内存,而数组在创建时需要分配固定大小的内存。......
  • 代码随想录|day3 链表 203.移除链表元素、707.设计链表、206.反转链表
    基础知识:代码随想录203.移除链表元素建议:本题最关键是要理解虚拟头结点的使用技巧,这个对链表题目很重要。这里主要记录用虚头的方法。即设置一个虚拟的头指针帮忙解题。先看代码:classSolution{publicListNoderemoveElements(ListNodehead,intval){ Li......
  • ROS2:节点
    节点ROS2中,节点是一个抽象的实体,可以代表某类特定功能的抽象集合体,可以存在于进程或线程中是ROS2的基础功能的载体,所有通信都需要通过节点来实现节点和节点执行器节点执行器executor是协调和调度节点运作的实体,并响应各类通信的回调结果每个进程有一个或多个节点执行器,每个节......