Leetcode24.两两交换链表中的节点

一、题目描述：

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

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

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

二、解决思路和代码

1. 解决思路

• 分析：借助一个头指针，以及三指针实现两两交换相邻的节点

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

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

    • cur: 指向两两交换的节点的第一个节点

    • last: 指向两两交换的节点的最后一个节点

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

      

  • step3: 修改cur, last, pre三个节点指针，实现两两节点交换操作，如下图所示：

    

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

2. 代码

    from typing import *
    class ListNode:
        def __init__(self, val=0, next=None):
            self.val = val
            self.next = next
        
    class Solution:
        def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
            if head==None or head.next==None:
                return head
            
            pre = ListNode(val=-1,next=head)
            cur = head
            last = head.next
            head = pre
            while True:
                ## pre, cur, last
                cur.next = last.next
                last.next = cur
                pre.next = last
                
                ## pre, last, cur
                if cur.next==None or cur.next.next==None: break
                pre = cur
                cur = pre.next
                last = pre.next.next
            return head.next