IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode 24. Swap Nodes in Pairs - 链表(Linked List)系列题5 -> 正文阅读

[数据结构与算法]LeetCode 24. Swap Nodes in Pairs - 链表(Linked List)系列题5

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

  • The number of nodes in the?list?is in the range?[0, 100].
  • 0 <= Node.val <= 100

题目大意:给定一个链表,要求把相邻的节点两两互换位置。是互换节点而不是改变节点值。

本题可以用递归和迭代两种解法。

解法1:递归法,当链表里节点个数小于等于1时,不需要处理直接返回。否则把链表分成两部分:前两个节点和剩余链表部分。将前两个节点互换位置,链表剩余部分看成一个新的链表做递归处理,处理完之后原来的头节点变成新的第二个节点并指向递归返回的头节点,原来的第二个节点变成了新的头节点并指向原来的头节点。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        p1, p2, p3 = head, head.next, head.next.next
        p2.next = p1
        p1.next = self.swapPairs(p3)
        
        return p2

解法2,迭代法,基本逻辑跟递归法差不多,每一次循环处理两个节点。定义两个指针(cur, pre),一个指向当前节点,一个指向前一个节点,当节点数少于2(cur或cur.next为空)时循环终止,否则循环继续交换cur和cur.next节点。整个处理过程涉及4个节点:父节点(pre),当前节点(cur),子节点(cur.next),孙节点(cur.next.next),暂存孙节点,父节点的next指向子节点,子节点的next指向当前节点,当前节点的next指向孙节点,更新两个指针pre = cur, cur = tmp使循环继续。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        preHead = ListNode(0, head)
        
        pre, cur = preHead, head
        while cur and cur.next:
            tmp = cur.next.next
            pre.next = cur.next
            cur.next.next = cur
            pre = cur
            cur.next = tmp
            cur = tmp
        
        return preHead.next

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-01-01 14:11:59  更:2022-01-01 14:13:09 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 17:29:28-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码