LeetCode 24：交换链表
快来点我去练习-------GO
题意
两两交换链表相邻节点的值，返回交换后的链表。
示例输入：head = [1, 2, 3, 4]
输出： [2, 1, 4, 3]
题目解析
水题，难度中等。
这道题要求不能只是单纯的改变节点内部得值，需要进行实际的节点交换。
和反转链表一样，这类链表题思维上没有难度，就是每次从链表上截取两个节点进行交换。
主要是考察代码实现能力。
这道题我用带虚拟头节点的单链表实现。
虚拟头节点（其实我以前都叫头节点我就叫虚拟头节点），可能很多人叫做哨兵节点，放在第一个元素的节点之前，数据域一般没意义。
图解先建立一个带虚拟头节点的单链表。
PS：此处代码为 Python（”代码实现“小节处有 Java 代码，下同）。
链表节点类
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
### 创建虚拟节点dummyHead = ListNode(-1)
复制代码
因为每次要截取两个节点进行交换，初始建立 3 个指针 pre，p 和 q。
其中 pre 指向虚拟头节点，p 指向链表首节点，q 指向链表的第 2 个节点。
pre = dummyHeadp = headq = p.next
复制代码
节点两两交换主要分为 3 步。
第 1 步：pre 的后继指针 next 指向 q，即 pre.next = q。
第 2 步：p 的后继指针 next 指向 q 的后继节点，即 p.next = q.next。
第 3 步：那就剩了 q 的后继指针 next 指向 p，即 q.next = p。
所以第一次交换完，链表变成了：
pre.next = qp.next = q.nextq.next = p
复制代码
接下来就是 pre、p 和 q 指针同时右移。
pre = pp = p.nextq = p.next
复制代码
继续重复上述 3 步操作。
本方法遍历一遍链表，时间复杂度为 O(n)，空间复杂度为 O(1)。
代码实现
Python 代码实现
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def swapPairs(self, head: ListNode) -> ListNode:
# 空链表或者只有一个节点，直接返回 if not head or head.next == None: return head
# 创建虚拟节点 dummyHead = ListNode(-1)
# 初始化pre、p 节点 pre = dummyHead p = head
# 必须是节点数是偶数个的时候才能交换 # 如果最后只剩下一个节点，即链表是奇数个节点，最后一个不用反转 # 比如 head = [1,2, 3, 4, 5],输出 [2, 1, 4, 3, 5] while p and p.next: # 初始化 q 节点 q = p.next
# 交换节点 3 步走 pre.next = q p.next = q.next q.next = p # 指针右移 pre = p p = p.next # 返回链表 return dummyHead.next
复制代码
Java 代码实现
// 虚拟头结点class Solution { public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode prev = dummyNode;
while (prev.next != null && prev.next.next != null) { ListNode temp = head.next.next; // 缓存 next prev.next = head.next; // 将 prev 的 next 改为 head 的 next head.next.next = head; // 将 head.next(prev.next) 的next，指向 head head.next = temp; // 将head 的 next 接上缓存的temp prev = head; // 步进1位 head = head.next; // 步进1位 } return dummyNode.next; }}
复制代码
图解交换链表到这就结束啦。
按照我的图解在纸上画一下加深印象，步骤不要出错。
评论