【力扣Leetcode题解系列之0024—两两交换链表中的节点】
·
零、力扣第24题“两两交换链表中的节点”是一道链表操作类的中等难度题目。
- 题目描述：给定一个链表，要求两两交换其中相邻的节点，并返回交换后链表的头节点，且只能进行节点交换，不能修改节点内部的值。
- 示例
- 示例1：输入
head = [1,2,3,4]，输出[2,1,4,3]。 - 示例2：输入
head = []，输出[]。 - 示例3：输入
head = [1]，输出[1]。
- 示例1：输入
- 提示
- 链表中节点的数目在范围
[0, 100]内。 0 <= Node.val <= 100。
- 链表中节点的数目在范围
- 解题思路
- 递归法：可以通过递归的方式来解决。递归的终止条件是链表为空或者只有一个节点。对于至少有两个节点的链表，先交换前两个节点，然后将第一个节点的下一个指针指向下一对节点交换后的头节点，最后返回交换后的新头节点。
- 迭代法：可以引入虚拟头节点，使用三个指针
prev（指向待交换节点对的前一个节点）、node1（待交换节点对的第一个节点）、node2（待交换节点对的第二个节点）。在循环中，判断prev的下一个节点和下下个节点是否存在，若存在则进行交换操作，更新指针，继续循环，直到遍历完整个链表。
一、常用解法
迭代法
- 思路：
- 首先设置一个哑节点（dummy node），它的
next指针指向链表头节点head。这是为了统一处理头节点交换和中间节点交换的情况，避免对头节点的特殊处理。 - 使用三个指针
prev、curr和nextNode。prev指针指向当前要交换的两个节点的前一个节点，curr指针指向当前要交换的两个节点中的第一个节点，nextNode指针指向当前要交换的两个节点中的第二个节点。 - 每次迭代时，先保存
curr的下一个节点（即nextNode），然后进行指针调整，将curr指向nextNode的下一个节点，nextNode指向curr，prev的next指针指向nextNode。这样就完成了一次两个相邻节点的交换。 - 然后将
prev移动到curr的位置，curr移动到curr的下一个节点位置，继续下一轮交换，直到没有相邻节点可交换（即curr或curr的下一个节点为空）。
- 首先设置一个哑节点（dummy node），它的
- 优点：迭代法的逻辑较为直观，通过逐步调整指针的方式完成节点交换，容易理解和实现。
递归法
- 思路：
- 递归的基本思想是将问题分解为更小的子问题。对于交换相邻节点的问题，先交换头两个节点，然后递归地处理剩余的链表。
- 在递归函数中，首先检查链表是否至少有两个节点（即
head和head.next都不为空）。如果是，则保存第二个节点nextNode，将head指向递归处理后的剩余链表的头节点（即head.next.next），然后将nextNode指向head，完成头两个节点的交换。 - 最后返回交换后的头节点，即
nextNode。
- 优点：递归法代码简洁，能够清晰地表达问题的递归结构。它通过不断将问题分解为更小的子问题来解决，在某些情况下更符合人们对问题的思考方式。
二、多语言实现
Python实现
- 迭代法
# 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):
dummy = ListNode(0)
dummy.next = head
prev = dummy
curr = head
while curr and curr.next:
nextNode = curr.next
curr.next = nextNode.next
nextNode.next = curr
prev.next = nextNode
prev = curr
curr = curr.next
return dummy.next
- 递归法
# 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):
if not head or not head.next:
return head
nextNode = head.next
head.next = self.swapPairs(nextNode.next)
nextNode.next = head
return nextNode
Java实现
- 迭代法
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode curr = head;
while (curr!= null && curr.next!= null) {
ListNode nextNode = curr.next;
curr.next = nextNode.next;
nextNode.next = curr;
prev.next = nextNode;
prev = curr;
curr = curr.next;
}
return dummy.next;
}
}
- 递归法
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode nextNode = head.next;
head.next = swapPairs(nextNode.next);
nextNode.next = head;
return nextNode;
}
}
C实现
- 迭代法
#include <stdio.h>
#include <stdlib.h>
// Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode dummy;
dummy.val = 0;
dummy.next = head;
struct ListNode *prev = &dummy;
struct ListNode *curr = head;
while (curr!= NULL && curr->next!= NULL) {
struct ListNode *nextNode = curr->next;
curr->next = nextNode->next;
nextNode->next = curr;
prev->next = nextNode;
prev = curr;
curr = curr->next;
}
return dummy.next;
}
C++实现
- 迭代法
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0);
dummy.next = head;
ListNode *prev = &dummy;
ListNode *curr = head;
while (curr && curr->next) {
ListNode *nextNode = curr->next;
curr->next = nextNode->next;
nextNode->next = curr;
prev->next = nextNode;
prev = curr;
curr = curr->next;
}
return dummy.next;
}
};
- 递归法
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head ||!head->next) {
return head;
}
ListNode *nextNode = head->next;
head->next = swapPairs(nextNode->next);
nextNode->next = head;
return nextNode;
}
};
Go实现
- 迭代法
package main
import "fmt"
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func swapPairs(head *ListNode) *ListNode {
dummy := &ListNode{}
dummy.Next = head
prev := dummy
curr := head
for curr!= nil && curr.Next!= nil {
nextNode := curr.Next
curr.Next = nextNode.Next
nextNode.Next = curr
prev.Next = nextNode
prev = curr
curr = curr.Next
}
return dummy.Next
}
- 递归法
package main
import "fmt"
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
nextNode := head.Next
head.Next = swapPairs(nextNode.Next)
nextNode.Next = head
return nextNode
}
三、算法复杂性分析
时间复杂度
- 迭代法和递归法：两种方法都需要遍历链表中的每个节点一次，因此时间复杂度均为 (O(n))，其中 (n) 是链表的长度。这是因为在最坏情况下，需要对链表中的每两个相邻节点进行一次交换操作。
空间复杂度
- 迭代法：除了返回的链表外，使用的额外空间为常数级，即用于创建哑节点和一些指针变量，空间复杂度为 (O(1))。
- 递归法：递归调用会使用额外的栈空间，递归的深度最大为链表的长度 (n)，因此空间复杂度为 (O(n))，这是由于在递归过程中，函数调用栈会保存每一层递归的状态，直到递归结束。
四、实现的关键点和难度
关键点
- 指针操作：无论是迭代法还是递归法，准确的指针操作是关键。在迭代法中，要正确调整
prev、curr和nextNode三个指针的指向，确保节点交换的正确性。在递归法中，要清晰地处理递归调用前后的指针关系，特别是head和nextNode指针的调整。 - 边界条件处理：处理好链表为空或只有一个节点的情况是重要的边界条件。在迭代法中，循环条件要确保在链表节点不足两个时停止交换。在递归法中，递归的终止条件就是处理链表为空或只有一个节点的情况，直接返回原链表。
- 哑节点的使用：使用哑节点可以统一处理头节点和中间节点的交换操作，简化代码逻辑。在迭代法中，哑节点的
next指针指向链表头节点，使得头节点的交换与其他节点的交换操作一致。
难度
- 递归理解与实现：递归法虽然代码简洁，但对于不熟悉递归思想的人来说，理解递归的调用过程和状态保存可能有一定难度。特别是在处理递归终止条件和递归调用返回结果的指针调整时，需要清晰的逻辑思维，否则容易出现错误。
- 指针操作细节：链表的指针操作容易出错，尤其是在同时处理多个指针时。在迭代法中，可能会出现指针移动顺序错误或遗漏指针更新的情况。在递归法中，对递归调用返回节点的指针设置也需要谨慎处理，否则可能导致链表结构混乱。
五、扩展及难度加深题目
扩展题目1：每k个节点一组进行交换
- 题目描述：给定一个链表和一个整数
k，将链表中每k个节点分为一组进行交换，并返回交换后链表的头节点。如果最后一组不足k个节点，则保持不变。 - 解题思路：在原迭代法的基础上，增加一个计数器，每
k个节点进行一次交换操作。可以通过嵌套循环来实现，外层循环控制分组，内层循环进行每组内的节点交换。每次交换完一组后，更新相关指针并继续下一组的交换。 - 代码示例（以Python为例）
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapKGroup(self, head, k):
dummy = ListNode(0)
dummy.next = head
prevGroupEnd = dummy
curr = head
while curr:
groupStart = curr
groupEnd = self.getGroupEnd(curr, k)
if not groupEnd:
break
nextGroupStart = groupEnd.next
self.reverseGroup(groupStart, groupEnd)
prevGroupEnd.next = groupEnd
groupStart.next = nextGroupStart
prevGroupEnd = groupStart
curr = nextGroupStart
return dummy.next
def getGroupEnd(self, head, k):
while head:
k -= 1
if k == 0:
return head
head = head.next
return None
def reverseGroup(self, start, end):
prev = None
curr = start
while curr!= end:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode
curr.next = prev
扩展题目2：交换链表中所有值相同的相邻节点
- 题目描述：给定一个链表，交换链表中所有值相同的相邻节点，并返回交换后链表的头节点。
- 解题思路：遍历链表，当发现相邻节点值相同时，进行交换操作。可以使用两个指针，一个指针
prev指向当前节点的前一个节点，另一个指针curr指向当前节点。如果curr和curr.next的值相同，则进行交换，并更新prev和curr的位置。继续遍历直到链表结束。 - 代码示例（以Python为例）
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapAdjacentSameValueNodes(self, head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
curr = head
while curr and curr.next:
if curr.val == curr.next.val:
nextNode = curr.next
curr.next = nextNode.next
nextNode.next = curr
prev.next = nextNode
else:
prev = curr
curr = curr.next
return dummy.next
难度加深题目1：在特定条件下交换相邻节点
- 题目描述：给定一个链表，对于相邻节点
A和B，如果A.val + B.val是一个素数，则交换这两个节点。返回交换后链表的头节点。 - 解题思路：遍历链表，对于每对相邻节点，计算它们值的和并判断是否为素数。如果是素数，则进行交换操作。可以使用迭代法，通过三个指针来完成交换过程，同时要注意处理好链表的边界情况。
- 代码示例（以Python为例）
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPrime(num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
class Solution:
def swapAdjacentIfPrimeSum(self, head):
dummy = ListNode(0)
dummy.next = head
prev = dummy
curr = head
while curr and curr.next:
if isPrime(curr.val + curr.next.val):
nextNode = curr.next
curr.next = nextNode.next
nextNode.next = curr
prev.next = nextNode
else:
prev = curr
curr = curr.next
return dummy.next
难度加深题目2：递归交换链表中每两个间隔为m的节点
- 题目描述：给定一个链表和一个整数
m，从链表头开始，每间隔m个节点，递归地交换接下来的两个节点，并返回交换后链表的头节点。如果剩余节点不足两个，则不进行交换。 - 解题思路：在递归函数中，首先移动指针
m步找到要交换的两个节点。如果找到两个节点，则进行交换，并递归处理交换后的链表部分。如果剩余节点不足两个，则直接返回原链表。 - 代码示例（以Python为例）
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def swapEveryTwoAfterM(self, head, m):
if not head or not head.next:
return head
curr = head
for _ in range(m - 1):
if not curr:
return head
curr = curr.next
if not curr or not curr.next:
return head
nextNode = curr.next
curr.next = self.swapEveryTwoAfterM(nextNode.next, m)
nextNode.next = curr
return nextNode
六、应用场合
- 数据加密与混淆：在数据加密或混淆算法中，对链表形式存储的数据进行节点交换操作，可以改变数据的顺序，增加数据的安全性和保密性。例如，在一些简单的加密方案中，通过特定规则交换链表节点，使得原始数据难以被直接获取。
- 链表结构优化：在某些需要对链表结构进行调整的算法中，交换相邻节点可以改变链表的拓扑结构，以满足特定的需求。例如，在一些图算法中，将图的邻接表表示为链表，通过交换链表节点来优化图的遍历顺序或数据访问模式。
- 排序算法的辅助操作：在一些链表排序算法中，交换相邻节点是实现排序的基本操作之一。例如，冒泡排序在链表上的实现，就需要通过交换相邻节点来逐步将最大（或最小）的元素“冒泡”到链表的末尾（或开头）。
- 游戏开发中的链表操作：在游戏开发中，链表常用于管理游戏对象的顺序。例如，在一个回合制游戏中，游戏角色的行动顺序可能存储在链表中。通过交换相邻节点，可以根据游戏规则动态调整角色的行动顺序，以实现更丰富的游戏逻辑和策略。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
20
0- 0
已为社区贡献6条内容
所有评论(0)