LeetCode第二十四题:两两交换链表中的节点 【python】

简介: 欢迎关注微信公众号 数据分析螺丝钉

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

问题描述

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

示例:

输入:1->2->3->4

输出:2->1->4->3

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

方法一:迭代法

解题步骤

创建哑节点:创建一个哑节点(dummy node),它的next指针指向链表的头节点。这样可以方便地处理头节点交换的特殊情况,并使得链表操作更加统一。

初始化指针:使用三个指针,prev初始化指向哑节点,curr指向prev.next(即链表的第一个节点),next指向curr.next(即链表的第二个节点)。

1. 遍历和交换节点:确保currnext不为空,因为这是交换的前提。

  • 更新prevnext指向next,实现第一步的节点交换。
  • 更新currnext指向next.next,将交换后的第二个节点连接到后面的节点。
  • nextnext指向curr,完成两节点的交换。
  • 移动prev指针到curr,准备下一对交换。
  • 更新currnext指向下一对可能交换的节点。

2. 返回结果:最终,prev将指向最后一个经过交换的节点,而哑节点的next指针指向新的头节点。返回dummy.next即可。

代码示例

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def swapPairs(head: ListNode) -> ListNode:
    dummy = ListNode(-1)
    dummy.next = head
    prev = dummy
    while prev.next and prev.next.next:
        curr = prev.next
        next = curr.next
        # Swapping
        prev.next = next
        curr.next = next.next
        next.next = curr
        # Move prev to curr
        prev = curr
    return dummy.next

算法分析

  • 时间复杂度:O(N),其中n是链表中的节点数。这是因为我们需要遍历整个链表来交换每对相邻节点。
  • 空间复杂度:O(1),我们只使用了有限的几个额外指针,不需要额外的空间来存储数据。

方法二:递归方法

解题步骤

1. 递归终止条件:

  • 如果链表为空(没有节点),或者只有一个节点(无法进行交换),递归应该终止。

2. 交换节点:

  • 对于链表的头两个节点,将第二个节点连接到第一个节点前面。

3. 递归函数调用:

  • 对于头两个节点之后的链表部分,递归调用该函数。

4. 连接已交换的部分:

  • 将前面步骤中已经交换好的部分连接到已经处理的链表的后面。

5. 返回值:

  • 每次递归调用应返回新的头节点,即原来的第二个节点。

代码示例

函数

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def swapPairs(head: ListNode) -> ListNode:
    # 如果链表为空或者只有一个节点,返回原链表
    if not head or not head.next:
        return head
    # 初始化两个节点
    first_node = head
    second_node = head.next
    # 递归处理余下的节点
    first_node.next = swapPairs(second_node.next)
    # 将第一个节点和第二个节点交换
    second_node.next = first_node
    # 返回新的头节点,即原来的第二个节点
    return second_node
# 辅助函数:打印链表
def printList(node):
    while node:
        print(node.val, end=" -> ")
        node = node.next
    print("None")
# 辅助函数:创建链表
def createList(values):
    dummy = ListNode(0)
    current = dummy
    for value in values:
        current.next = ListNode(value)
        current = current.next
    return dummy.next

调试
# 创建链表
input_list = createList([1, 2, 3, 4])
# 应用函数
swapped_list = swapPairs(input_list)
# 打印结果
printList(swapped_list)

输出
2 -> 1 -> 4 -> 3 -> None

算法分析

很抱歉,我无法回答这个问题,因为你没有提供任何文章供我评估。如果你能提供文章的话,我可以帮助你评估其质量。

  • 时间复杂度:O(N),其中 n 是链表中的节点数量。递归方法会访问每个节点一次,进行常数时间的操作(交换两个节点)。
  • 空间复杂度:O(N) 的递归调用栈空间,在最坏的情况下(当链表完全不为空时),递归深度可以达到 n/2 (每次递归处理两个节点)。

结论

如果链表长度不是非常大,或者对代码简洁性有更高要求,可以选择递归方法。

如果需要处理非常长的链表,或者环境对递归深度有严格限制(如某些嵌入式系统或限制了递归深度的编程环境),则迭代方法更为合适

对于实际应用,选择哪种方法(迭代或递归)应根据具体问题的需求和环境的限制来决定。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
6天前
|
前端开发 JavaScript UED
Python Web应用中的WebSocket实战:前后端分离时代的实时数据交换
【7月更文挑战第16天】在前后端分离的Web开发中,WebSocket解决了实时数据交换的问题。使用Python的Flask和Flask-SocketIO库,后端创建WebSocket服务,监听并广播消息。前端HTML通过JavaScript连接到服务器,发送并显示接收到的消息。WebSocket适用于实时通知、在线游戏等场景,提升应用的实时性和用户体验。通过实战案例,展示了如何实现这一功能。
|
21天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
16 2
|
21天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
21天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
21天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
2月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2