24题一组数据交换相邻节点

发表于 | 分类于
本文字数： 772 | 阅读时长 ≈ 1 分钟

交换相邻节点

难度：中等 思路：递归

一、题目描述

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

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

示例:

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

二、问题分析

链表中节点的交换是传统问题，两个指针解决问题，唯一要注意的是不能在交换过程中把链表给断开了，否则岂不是得不偿失？暴力法本可以解决一切，但是优雅的方法是递归，把相邻节点的交换搞定，然后递归把所有的节点串起来，简直是美滋滋啊。

三、代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def swapPairs(self, head):        
        # 防止只有一个节点或没有节点时报错
        if head and head.next:
            p = head
            q = head.next
            head = q
            # 第一次交换不需要考虑与前面的连接 三步法连接
            p.next = q.next
            q.next = p 
            # 开始递归
            p.next = self.swapPairs(p.next)
        else:
            if head:
                return head
            else:
                return None
        
        return head

复杂度分析

O(N)