目录

• • 一、题目描述：
  • 二、解决思路和代码
  • • 1. 解决思路
    • 2. 代码

一、题目描述：

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

1. 示例 1：
   • 输入：head = [1,2,3,4]
   • 输出：[2,1,4,3]
2. 示例 2：
   • 输入：head = []
   • 输出：[]
3. 示例 3：
   • 输入：head = [1]
   • 输出：[1]

• 提示：
  • 链表中节点的数目在范围 [0, 100] 内
  • 0≤Node.val≤1000 \leq Node.val \leq 1000≤Node.val≤100

二、解决思路和代码

1. 解决思路

• 分析：借助一个头指针，以及四指针实现 翻转K个一组 的节点

  • step1: 借助一个头节点，方便后续修改指针指向操作

  • step2: 借助三个指针：pre, cur, last

    • cur: 指向 一组k个节点 的第一个节点

    • last: 指向 一组k个节点 的最后一个节点

    • pre: 指向 待交换一组k个节点 的前一个节点

    • 例如，当 k=3 时，先找到 pre, cur, last 所指向的节点：

      

  • step3: 翻转k个一组链表

    • 翻转前链表的最后一个节点为翻转后链表的第一个节点，修改: pre.next=last
    • 使用头插法实现K个一组翻转链表的操作:
      • 借助一个临时指针temp，指向待翻转链表的第一个节点
        
        
        

  • step4: 重复step2, step3，直到遍历所有节点

2. 代码

    from typing import *class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:if k==1: return head## step1:pre = ListNode(val=-1, next=head)head = prewhile pre.next:## step2:   cur = last = pre.nextcount = 1while count1:temp = curcur = cur.nextcount -= 1temp.next = last.nextlast.next = tempif k-count==1: pre = temp## if cur==last: pre = tempreturn head.next