• 15链表-交换节点


    目录

    LeetCode之路——24. 两两交换链表中的节点

    分析:

    解法一:迭代

    解法二:递归



    LeetCode之路——24. 两两交换链表中的节点

    给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

    示例 1:

    img

    输入:head = [1,2,3,4]
    输出:[2,1,4,3]

    示例 2:

    输入:head = []
    输出:[]

    示例 3:

    输入:head = [1]
    输出:[1]

    提示:

    • 链表中节点的数目在范围 [0, 100]

    • 0 <= Node.val <= 100

    分析:
    解法一:迭代

    1.用哨兵节点正常模拟场景,迭代的方式完成交换。

    2.temp作为当前节点迭代,需要注意的是指针的赋值。

    ListNode node1 = temp.next;

    ListNode node2 = temp.next.next;

    temp.next = node2;

    node1.next = node2.next;

    node2.next = node1;

    class Solution {
        public ListNode swapPairs(ListNode head) {
            ListNode sentinel = new ListNode(-1);
            sentinel.next = head;
            ListNode temp = sentinel;
            while (temp.next != null && temp.next.next != null) {
                ListNode node1 = temp.next;
                ListNode node2 = temp.next.next;
                temp.next = node2;
                node1.next = node2.next;
                node2.next = node1;
                temp = node1;
            }
            return sentinel.next;
        }
    }
    解法二:递归

    1.递归的终止条件是链表中没有节点,或者链表中只有一个节点,此时无法进行交换。

    2.如果链表中至少有两个节点,则在两两交换链表中的节点之后,原始链表的头节点变成新的链表的第二个节点,原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后,更新节点之间的指针关系,即可完成整个链表的两两交换。

    // 递归
    class Solution {
        public ListNode swapPairs(ListNode head) {
            // base case 退出提交
            if(head == null || head.next == null) return head;
            // 获取当前节点的下一个节点
            ListNode next = head.next;
            // 进行递归
            ListNode newNode = swapPairs(next.next);
            // 这里进行交换
            next.next = head;
            head.next = newNode;
    ​
            return next;
        }
    } 
    • 时间复杂度:O(n)

    • 空间复杂度:O(n)

  • 相关阅读:
    Python语言:散修笔记
    Oracle中序列
    java-php-python-ssm旅游路线规划系统计算机毕业设计
    微信小程序通过 movable-area 做一个与vuedraggable相似的上下拖动排序控件
    在ubuntu20.04上面跑通rocket-chip仿真,用rocket-tools工具
    C# OCR服务测试程序
    模拟卷Leetcode【普通】061. 旋转链表
    鲜花商城|基于Springboot实现鲜花商城系统
    git使用
    记一次mysql事务并发优化
  • 原文地址:https://blog.csdn.net/Elaine2391/article/details/133590166