每日一题：Leetcode-24 两两交换链表中的节点

力扣题目

解题思路

java代码

力扣题目：

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

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

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

解题思路：

算法原理：

• 通过递归的方式逐步交换相邻节点。

思路：

• 首先判断链表是否为空或者只有一个节点，如果是则直接返回该链表。
• 然后找到当前的两个节点，将它们交换位置，并让第一个节点（原来的第二个节点）的下一个节点指向递归处理后面节点后的结果，同时让原来的第一个节点成为新的第二个节点的下一个节点。

代码分析：

• 在 swapPairs 方法中，先进行边界判断。
• 接着确定新的头节点为原来的第二个节点。
• 然后进行节点交换的操作，并通过递归继续处理后面的节点。

时间复杂度：O（n），需要遍历整个链表。
空间复杂度：O（n），递归调用栈的空间消耗。

java代码：

package org.example.mouth8;

public class Leetcode24 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head = swapPairs(head);
        while (head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项