hazel'blog
0%

发表于 分类于
本文字数： 445 阅读时长 ≈ 1 分钟

哈希表-快乐数

题目链接

这道题也是用C++的unordered_set比较简单，题目中提到无限循环，也就是sum是出现过的，也就陷入了无限循环了已经，这个时候就返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int getSum(int n){
        int sum = 0;
        while(n){
            sum += (n % 10)*(n % 10);
            n /= 10;
        }
        return sum;   
    }
    bool isHappy(int n) {
        unordered_set<int> sumSet;
        while(1){
            int sum = getSum(n);
            if(sum == 1)return true;
            if(sumSet.find(sum) != sumSet.end())
                return false;
            else
                sumSet.insert(sum);
            n = sum;
        }


    }
};

发表于 分类于
本文字数： 447 阅读时长 ≈ 1 分钟

哈希表-两个数组的交集

题目链接

这道题用C++的unordered_set比较简单，这个容器是个无序的set容器，容器内部存的值都不相等，并且不能被修改，并非以键值对的形式存储数据，而是直接存储数据的值。（键和值相等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isAnagram(char * s, char * t){
    int record[26] = {0};
    int len_s = strlen(s);
    int len_t = strlen(t);

    for(int i = 0; i < len_s; i++){
        record[s[i]-'a']++;
    }
    for(int j = 0; j < len_t; j++){
        record[t[j]-'a']--;
    }
    for(int k = 0; k < 26; k++){
        if(record[k] != 0)return false;
          
    }
    return true; 
}

发表于 分类于
本文字数： 539 阅读时长 ≈ 1 分钟

哈希表-有效的字母异位

题目链接

遍历字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可， 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool isAnagram(char * s, char * t){
    int record[26] = {0};
    int len_s = strlen(s);
    int len_t = strlen(t);

    for(int i = 0; i < len_s; i++){
        record[s[i]-'a']++;
    }
    for(int j = 0; j < len_t; j++){
        record[t[j]-'a']--;
    }
    for(int k = 0; k < 26; k++){
        if(record[k] != 0)return false;
          
    }
    return true; 
}

发表于 分类于
本文字数： 680 阅读时长 ≈ 1 分钟

链表-对链表进行插入排序

题目链接

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct ListNode* insertionSortList(struct ListNode* head){
    typedef struct ListNode ListNode;
    ListNode* dummyNode = (ListNode*)malloc(sizeof(ListNode));
    dummyNode->next = head;
    ListNode* cur = head->next;
    ListNode* LastStored = head;
    while(cur){
        if(cur->val >= LastStored->val)LastStored = LastStored->next;
        else{
            ListNode* prev = dummyNode;
            while(prev->next->val <= cur->val)prev = prev->next;

            LastStored->next = cur->next;
            cur->next = prev->next;
            prev->next = cur;
            
        }
        cur = LastStored->next;
    }
    return dummyNode->next;
        
    
}

发表于 分类于
本文字数： 4.1k 阅读时长 ≈ 4 分钟

参考文章：详解ELF文件、ELF文件结构

其实PE文件和ELF文件结构比较类似，学过PE文件后，ELF文件就很好懂。

通俗点说由汇编器和链接器生成的文件都属于ELF文件。通常我们接触的ELF文件主要有以下三类：

  • 可重定位文件（relocatable file） ，一般为.o文件。可以被链接成可执行文件或共享目标文件。静态链接库属于可重定位文件。
  • 可执行文件（excutable file）它保存了适合直接加载到内存中执行的二进制程序。
  • 共享库文件（shared object file）一般为.so文件。一种特殊的可重定位目标文件，可以在加载或者运行时被动态的加载进内存并链接。

image-20220322201522334

image-20220322203524439

Note:段（Segment）与节（Section）的区别。很多地方对两者有所混淆。段是程序执行的必要组成，当多个目标文件链接成一个可执行文件时，会将相同权限的节合并到一个段中。相比而言，节的粒度更小。

ELF文件主要由四部分组成：

  • ELF Header
  • ELF Program Header Table(程序头)
  • ELF Section Header Table(节头表)
  • ELF sections

ELF Header

ELF Header其实对应的是一个结构体，该结构体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define EI_NIDENT 16

   typedef struct {                     
       unsigned char e_ident[EI_NIDENT];
       uint16_t      e_type;            
       uint16_t      e_machine;         
       uint32_t      e_version;         
       ElfN_Addr     e_entry;           
       ElfN_Off      e_phoff;           
       ElfN_Off      e_shoff;           
       uint32_t      e_flags;           
       uint16_t      e_ehsize;          
       uint16_t      e_phentsize;       
       uint16_t      e_phnum;           
       uint16_t      e_shentsize;       
       uint16_t      e_shnum;           
       uint16_t      e_shstrndx;        
   } ElfN_Ehdr;
1
2
ElfN_Addr       Unsigned program address, uintN_t
ElfN_Off        Unsigned file offset, uintN_t
  • e_ident：包含一个magic number、ABI信息，该文件使用的平台、大小端规则
  • e_type：文件类型, 表示该文件属于可执行文件、可重定位文件、core dump文件或者共享库
  • e_entry: 表示程序执行的入口地址，规定ELF程序的入口虚拟地址，操作系统在加载完该程序后从这个地址开始执行进程的指令。可重定位指令一般没有入口地址，则该值为0
  • e_phoff: 表示Program Header的入口偏移量（以字节为单位）
  • e_shoff: 表示Section Header的入口偏移量（以字节为单位）
  • e_flags: 保存了这个ELF文件相关的特定处理器的flag
  • e_ehsize: 表示ELF Header大小（以字节为单位）
  • e_phentsize: 表示Program Header大小（以字节为单位）
  • e_phnum: 表示Program Header的数量 （十进制数字）
  • e_shentsize: 表示单个Section Header大小（以字节为单位）
  • e_shnum: 表示Section Header的数量 （十进制数字）
  • e_shstrndx: 表示字符串表的索引，字符串表用来保存ELF文件中的字符串，比如段名、变量名。 然后通过字符串在表中的偏移访问字符串。

magic：通过判断该字段可以确定文件格式和类型。如：ELF的可执行文件格式的头4个字节为0x7F、e、l、f；Java的可执行文件格式的头4个字节为c、a、f、e；如果被执行的是Shell脚本或perl、python等解释型语言的脚本，那么它的第一行往往是#!/bin/sh或#!/usr/bin/perl或#!/usr/bin/python，此时前两个字节#和!就构成了魔数，系统一旦判断到这两个字节，就对后面的字符串进行解析，以确定具体的解释程序路径。

ELF Section Header Table

ELF 节头表是一个节头数组。每一个节头都描述了其所对应的节的信息，如节名、节大小、在文件中的偏移、读写权限等。编译器、链接器、装载器都是通过节头表来定位和访问各个节的属性的。

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct {
    uint32_t   sh_name;
    uint32_t   sh_type;
    uint64_t   sh_flags;
    Elf64_Addr sh_addr;
    Elf64_Off  sh_offset;
    uint64_t   sh_size;
    uint32_t   sh_link;
    uint32_t   sh_info;
    uint64_t   sh_addralign;
    uint64_t   sh_entsize;
} Elf64_Shdr;

  • sh_name：表示该section的名字,节名是一个字符串，保存在一个名为.shstrtab的字符串表（可通过Section Header索引到）。sh_name的值实际上是其节名字符串在.shstrtab中的偏移值。

  • sh_type：表示该section中存放的内容类型，比如符号表，可重定位段等。

  • sh_flags： 表示该section的一些属性，比如是否可写，可执行等。

  • sh_addr： 表示该section在程序运行时的内存地址

  • sh_offset： 如果该节存在于文件中，则表示该节在文件中的偏移；否则无意义，如sh_offset对于BSS 节来说是没有意义的

  • sh_size： 表示该section的大小

  • sh_link： 配合sh_info保存section的额外信息

  • sh_info：保存该section相关的一些额外信息

  • sh_addralign：表示该section需要的地址对齐信息

  • sh_entsize：有些section里保存的是一些固定长度的条目，比如符号表。对于这些section来讲，sh_entsize里保存的就是条目的长度。

    sh_type（节类型）

image-20220322205037066

sh_link、sh_info(节链接信息)

如果节的类型是与链接相关的（无论是动态链接还是静态链接），如重定位表、符号表、等，则sh_link、sh_info两个成员所包含的意义如下所示。其他类型的节，这两个成员没有意义。

image-20220322205250620

ELF Sections

在ELF文件中，数据和代码分开存放的，这样可以按照其功能属性分成一些区域，比如程序、数据、符号表等。这些分离存放的区域在ELF文件中反映成section。ELF文件中典型的section如下：

  • .text: 已编译程序的二进制代码
  • .rodata: 只读数据段，比如常量
  • .data: 已初始化的全局变量和静态变量
  • .bss: 未初始化的全局变量和静态变量，所有被初始化成0的全局变量和静态变量(记得与PE文件区分开)
  • .sysmtab: 符号表，它存放了程序中定义和引用的函数和全局变量的信息
  • .debug: 调试符号表，它需要以'-g'选项编译才能得到，里面保存了程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C文件
  • .line: 原始的C文件行号和.text节中机器指令之间的映射
  • .strtab: 字符串表，内容包括.symtab和.debug节中的符号表

特殊的，
1）对于可重定位的文件，由于在编译时，并不能确定它引用的外部函数和变量的地址信息，因此，编译器在生成目标文件时，增加了两个section：

  • .rel.text 保存了程序中引用的外部函数的重定位信息，这些信息用于在链接时重定位其对应的符号。
  • .rel.data 保存了被模块引用或定义的所有全局变量的重定位信息，这些信息用于在链接时重定位其对应的全局变量。

2）对于可执行文件，由于它已经全部完成了重定位工作，可以直接加载到内存中执行，所以它不存在.rel.text和.rel.data这两个section。但是，它增加了一个section：

  • .init: 这个section里面保存了程序运行前的初始化代码

重定位表是一个Elf_Rel类型的数组结构，每一项对应一个需要进行重定位的项。
其成员含义如下表所示：

image-20220322205729738

ELF Program Header Table

在可执行文件中，ELF header下面紧接着就是Program Header Table。它描述了各个segment在ELF文件中的位置以及在程序执行过程中系统需要准备的其他信息。它也是用一个结构体数组来表示的。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef uint64_t  Elf64_Addr;
typedef uint64_t  Elf64_Off;
typedef uint32_t  Elf64_Word;
typedef uint64_t  Elf64_Xword;

typedef struct {
    Elf64_Word      p_type;         // 4
    Elf64_Word      p_flags;        // 4
    Elf64_Off       p_offset;       // 8
    Elf64_Addr      p_vaddr;        // 8
    Elf64_Addr      p_paddr;        // 8
    Elf64_Xword     p_filesz;       // 8
    Elf64_Xword     p_memsz;        // 8
    Elf64_Xword     p_align;        // 8
} Elf64_Phdr;
  • p_type：描述了当前segment是何种类型的或者如何解释当前segment，比如是动态链接相关的或者可加载类型的等
  • p_flags：保存了该segment的flag
  • p_offset：表示从ELF文件到该segment第一个字节的偏移量
  • p_vaddr：表示该segment的第一个字节在内存中的虚拟地址
  • p_paddr：对于使用物理地址的系统来讲，这个成员表示该segment的物理地址
  • p_filesz：表示该segment的大小，以字节表示
  • p_memsz：表示该segment在内存中的大小，以字节表示
  • p_align：表示该segment在文件中或者内存中需要以多少字节对齐

发表于 分类于
本文字数： 437 阅读时长 ≈ 1 分钟

链表-环形链表II

题目链接

这道题感觉还是有点难，看了这篇题解觉得很清楚详细。其实代码很简单，理清楚逻辑很重要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode* fast = head;
    ListNode* slow = head;
   
    while(true){
        if(fast == NULL || fast->next == NULL)return NULL;
        fast =fast->next->next;
        slow = slow->next;
        if(fast == slow)break;
    }
    fast = head;
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }

    return fast;

}

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

参考文章：看雪虚拟机保护技术浅谈，人肉跟踪VMProtect入口

虚拟机概览

​ 所谓虚拟机保护技术，是指将代码翻译为机器和人都无法识别的一串伪代码字节流（字节码）；在具体执行时再对这些伪代码进行一一翻译解释，逐步还原为原始代码并执行。字节码它是由指令执行系统定义的一套指令和数据组成的一串数据流。

​ 负责用于翻译伪代码并负责具体执行的子程序就叫做虚拟机VM,好似一个抽象的CPU。它以一个函数的形式存在，函数的参数就是字节码的内存地址。

image-20220322164833574

​ 这张图是一个虚拟机执行时的整图概述，VStartVM部分初始化虚拟机，VMDispatcher负责调度这些Handler，Handler可以理解为一个个的子函数(功能代码)，它是每一个伪指令对应的执行功能代码.

为什么要出现一条伪指令对应着一个Handler执行模块呢？

这和虚拟机加壳的指令膨胀有关，被虚拟机加壳后，同样一条指令被翻译成了虚拟伪指令，
一条虚拟伪指令往往对应着好几倍的等效代码，当中可能还加入了花指令，整个Handler加起来可能就等效为原本的一条x86汇编指令。

​ Bytecode就是虚拟伪指令，在程序中，VMDispatcher往往是一个类while结构，不断的循环读取伪指令，然后执行。

虚拟机架构

​ 虚拟机不可能针对每一种具体情况都进行翻译处理。必须对所有可能遇到的指令先进行抽象归类，然后分解为若干简单的小指令，再交由各个专门的子程序（handler）去处理。

三元式代码（3地址代码）

即不论多么复杂的赋值公式，都可以分解为数个3地址代码式序列。1段3地址代码只完成1次运算，譬如1次二目运算、1次比较，或者1次分支跳转运算。论多么复杂的指令，都可以分解为一串不可再分割的原子指令序列。

​ 虚拟机（CPU）的体系架构可分为3种，基于堆栈的(Stack based)，基于寄存器的(Register based)和3地址机器。基于堆栈的虚拟机体系架构需要频繁操作堆栈，其使用的虚拟寄存器保存在堆栈中，每个原子指令的handler都需要push,pop。譬如指令add,基于堆栈的CPU首先从堆栈里Pop两个数，然后将两数相加，再把和Push到堆栈。Add指令只占用1个字节。而基于寄存器的CPU对应指令为 add Reg1,Reg2，需要3个字节。

​ 虚拟机保护技术，就是把基于寄存器的CPU代码，改造成基于堆栈的CPU的伪代码。然后再由基于堆栈的虚拟机(CPU)对伪代码解释执行。

​ VStartVM是虚拟机的入口，负责保存运行环境(各个寄存器的值)、以及初始化堆栈(虚拟机使用的变量全部在堆栈中)。Bytecode是伪代码；VMDispatcher对伪代码逐个阅读处理，然后分发给下面的各个子程序(Handler)。 加壳程序先把已知的X86指令解释成了字节码，放在PE文件中，然后将原处代码删掉，改成类似的代码进入虚拟机执行循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
push bytecode         ;伪代码地址 ，作为参数
jmp   VstartVM
VStartVM:
   push eax   ;将寄存器压入堆栈,后面会由伪指令取出并存放到VMContext中;此处也可以加入一些随机特征用于迷惑
   push ebx
   push ecx
   push edx
   push esi
   push edi
   push ebp
   pushfd
   mov esi ,[esp+0x20]   ;esp+0x20指向VStartVM的参数,即伪代码的内存地址
   mov ebp,esp           ;ebp指向当前堆栈
   Sub esp,0x200         ;在堆栈中开辟0x200字节,存放VMcontext
   mov edi,esp           ;edi指向VMcontext
   Sub esp,0x40          ;到这里，才到达VM真正使用的堆栈，不一定非要0x40字节
VMDispatcher:
        Mov eax,byte ptr[esi]  ;获得伪代码 bytecode
        Lea esi,[esi+1]         
        Jmp dword ptr [eax*4+JumpAddr];跳到Handler执行处，由加壳引擎填充
                                      ;每读一个byte就跳到函数表模拟执行代码。(堆栈型CPU的指令短，1字节足够)
                                      ;JUMPADDR就是一张函数表（有点类似VTBL或者switch-case表），
VM_END                            ;VM结束标记

image-20220322150225897

​ 初始化后堆栈如图 ：edi指向VMcontext；esi指向伪代码的地址；ebp指向真实堆栈的栈顶; 这三个寄存器在VM内不要再改了。
VMContext是虚拟机VM使用的虚拟环境结构：

1
2
3
4
5
6
7
8
9
10
11
Struct VMContext
 {
     DWORD v_eax;
     DWORD v_ebx;
     DWORD v_ecx;
     DWORD v_edx;
     DWORD v_esi;
     DWORD v_edi;
     DWORD v_ebp;
     DWORD v_efl;
  }

用简单的add指令作为示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Vadd:                            ;virtual add
        Mov eax,[esp+4]          ;取源操作数
        Mov ebx,[esp]            ;取目的操作数
        Add ebx,eax              ;
        Add esp,8                ;把参数从堆栈中删掉，平衡堆栈
        Push ebx                 ;把结果压入堆栈.而原有的add命令的参数，我们需要翻译为 push 命令 。根据push 的对象不同，需要不同的实现：
vPushReg32:                      ;寄存器入栈 。esi指向字节码的内存地址
      Mov eax,dword ptr[esi]     ;从伪代码(字节码)中获得寄存器在VMcontext结构中的偏移地址
      Add esi,4                  ;VMcontext结构保存了各个寄存器的值。该结构保存在堆栈内。
      Mov eax,dowrd ptr [edi +eax]   ;得到寄存器的值。edi指向VMcontext结构的基址
      Push eax                    ;压入堆栈
      Jmp VMDispatcher            ;任务完成,跳回任务分派点
vPushImm32:                       ;立即数入栈
      Mov eax,dword ptr[esi]      ;字节码，不用翻译就是了
      Add esi,4
      Push eax                    ;立即数入栈
      Jmp VMDispatcher
     有Push指令了，也得有Pop指令：
vPopReg32:
      Mov eax,dword,ptr[esi]     ;从伪代码(字节码)中获得寄存器在VMcontext结构中的偏移地址
      Add esi,4
      Pop dword ptr [edi+eax]    ;弹回寄存器
      Jmp VMDispatcher
 ================================================================
      Add esi,eax
        ;转换为虚拟机的指令如下:
      vPushReg32 eax_index
      vPushReg32 esi_index
      Vadd
      vPopReg32 esi_index      ;不弹eax_index，它作为返回结果保存在堆栈里

image-20220322153743802

​ 上图是参考文章中的图，和我自己画的那个差不多，区分了颜色来说一下蓝-橙-黄部分作用（一条vmp指令的执行）。

    * 蓝色：加载并解密字节码。
  • 橙色：根据字节码数值计算出handler地址。
  • 黄色：执行该handler逻辑。

​ 前十几个蓝橙黄组合都是一种handler，执行的是一种vPop操作，如上图箭头，是将真实寄存器的值移动到VMcontext区域，一个vPop移动一个值。

​ 后十几个蓝橙黄组合

image-20220322160413449

​ 最后一个vRet，将压入vmp运算栈中vmp虚拟寄存器值，更新到真实cpu寄存器中，至此，退出虚拟机。

image-20220322160612021

发表于 更新于 分类于
本文字数： 847 阅读时长 ≈ 1 分钟

链表-链表相交

题目链接

还是简单的双指针问题，我感觉leetcode这道题还是有点问题，skipA/B都没在参数里面
（这道题目看的是节点的地址是否相等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
typedef struct ListNode ListNode;
   ListNode* ListNodeA = headA;
   ListNode* ListNodeB = headB;
   int lenA = 0;
   int lenB = 0;
   int lenAB = 0;
   while (ListNodeA != NULL) {
       lenA++;
       ListNodeA = ListNodeA->next;
   }
   while (ListNodeB != NULL) {
       lenB++;
       ListNodeB = ListNodeB->next;
   }

   if (lenA > lenB) {
       ListNodeA = headA;
       ListNodeB = headB;
       lenAB = lenA - lenB;
   }
   else {
       ListNodeA = headB;
       ListNodeB = headA;
       lenAB = lenB - lenA;
   }

   while (lenAB-- && ListNodeA != NULL) { 
       ListNodeA = ListNodeA->next;
   }

   while (ListNodeA != NULL) {
       if (ListNodeA == ListNodeB)
           return ListNodeA;
       ListNodeA = ListNodeA->next;
       ListNodeB = ListNodeB->next;
   }
   return NULL;
}

发表于 分类于
本文字数： 871 阅读时长 ≈ 1 分钟

链表-删除链表的倒数第n个节点

题目链接

fast先移动n+1个节点，与slow之间要相隔n个节点，然后fast需要和slow一起移动，直到fast指向末尾（C++/C记得释放被删除的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    typedef struct ListNode ListNode;
    ListNode* dummyNode = (ListNode*)malloc(sizeof(ListNode));
    dummyNode->next = head;
    ListNode* fast = dummyNode;
    ListNode* slow = dummyNode;
    ListNode* tmp;
    while(fast && n--){
        fast = fast->next;
    }
    fast = fast->next;
    while(fast){
        fast = fast->next;
        slow = slow->next;
    }
    tmp = slow->next;
    slow->next = slow->next->next;
    free(tmp);
    return dummyNode->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fakehead = ListNode(next = head)
        slow, fast = fakehead, fakehead
        while (n):         # python没有--或者++
            fast = fast.next
            n -= 1
        fast = fast.next
        while(fast):
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return fakehead.next

发表于 分类于
本文字数： 876 阅读时长 ≈ 1 分钟

链表-两两交换链表中的节点

题目链接

今天试了一下python编程，还是得慢慢把python熟练起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct ListNode* swapPairs(struct ListNode* head){
    typedef struct ListNode ListNode;
    ListNode *dummyNode = (ListNode *)malloc(sizeof(ListNode));
    dummyNode->next = head;    //后面好返回值
    struct ListNode* cur = dummyNode;
    while(cur->next && cur->next->next ){
        struct ListNode* tmp;
        struct ListNode* tmp1;
        tmp = cur->next;
        tmp1 = cur->next->next->next;//保留中途变换的时候会没有被指向的两个值
        cur->next = cur->next->next;
        cur->next->next = tmp;
        cur->next->next->next = tmp1;
        cur = cur->next->next;

    }

    return dummyNode->next;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyNode = ListNode(next=head)
        cur = dummyNode

        while cur.next and cur.next.next:
            left = cur.next
            right = cur.next.next

            left.next = right.next
            right.next = left
            cur.next = right

            cur = cur.next.next
        return dummyNode.next