博客

本章收录于专栏：一起来刷题，持续更新中……

更多精彩文章，欢迎大家关注我，一起学习，一起进步~

推荐专栏：大道至简之机器学习算法系列

本节题目来源于LeetCode 两两交换链表中的节点

题目描述：

 这是一道中等题，但是是链表的常规操作题，需要对链表结构足够熟悉，就能轻松解答。推荐解题前，自己画个简图，然后一步一步改变节点连接，一目了然。

解题思路如下：

（1）因为要交换链表节点，所以要考虑到交换前后，两个节点的旧指向和新指向的变化，为了保证本轮交换不影响到下一轮，那么我们就需要将下一轮待交换子链表的首节点存起来，定义两个指针，一个指针prev指向待交换子链表的首节点，另一个指针为原始链表的头结点的复制品p：

temp = p.next.next

 （2）接下来就开始调整两个节点的指向。首先，让prev的旧连接断开，让prev新连接指向2（p.next）：

prev.next = p.next

 （3）再将2的指向由原来的指向3，改为指向1（p）：

prev.next.next = p

 （4）随后将1（p）的指向由原来的2，指向下一轮子链表的头结点3（temp）：

p.next = temp

调整一下布局，更加清晰：

 （5）通过以上几步，我们将1和2交换了位置。准备进行下一轮交换，在此之前，我们要把prev和p放到它们该有的初始位置，即一个指向待交换子链表的头结点，另一个是待交换子链表的头结点的复制品：

prev = p
p = temp

 调整一下布局：

 Ok，第一轮交换完成。后续操作就是重复上述步骤即可。完整代码：

# Definition for singly-linked list.
# 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 not head or not head.next:
            return head
        dummy = ListNode(None)
        dummy.next = head
        prev = dummy
        p = head
        while p and p.next:
            temp = p.next.next
            prev.next = p.next
            prev.next.next = p
            p.next = temp
            prev = p
            p = temp
        return dummy.next