leetcode 24 两两交换链表中的节点

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs  

解题思路一

考虑两个变量值交换的情况，引入中间变量temp，然后交换两个变量的值。

变量 a，b 引入中间变量 temp temp = a a = b b = temp

同理，引入中间变量temp，完成链表节点的交换。

## 链表的元素是连在一起的，a->b->c ## 所以在交换a，b后，应该为 b->a->c ## 所以不仅要保证a，b位置互换，a还要指向c class Solution: def swapPairs(self, head: ListNode) -> ListNode: p = ListNode(0) p.next = head p1 = p # 加一个头节点 while p.next and p.next.next: # 保证有两个可交换的节点 temp = p.next # 引入中间变量temp p.next = p.next.next # b 换到 a前面 temp.next = p.next.next # a.next = c a指向c p.next.next = temp # b.next = a b指向a p = p.next.next # 从交换后a所在的位置继续下一次交换 return p1.next

解题思路二

递归：递归体、递归终止条件。

# 没有下一个节点，或者只剩下一个节点时，递归终止，返回当前节点。 # 两个节点进行交换，a.next = b.next a->c a指向c # 然后 b.next = a b指向a # 返回b，因为每一次递归执行时，b都被换到了前面。 class Solution: def swapPairs(self, head: ListNode) -> ListNode: if not head or not head.next: return head a = head b = head.next a.next = self.swapPairs(b.next) b.next = a return b