JAVA练习298- 两两交换链表中的节点

题目概览给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。示例 1输入head [1,2,3,4]输出[2,1,4,3]示例 2输入head []输出[]示例 3输入head [1]输出[1]提示链表中节点的数目在范围[0, 100]内0 Node.val 100来源24. 两两交换链表中的节点 - 力扣LeetCode解题分析方法一模拟 迭代令相邻的两个节点为 ab交换的过程就是a 的前一个节点指向 bb 指向 aa 指向 b 的后一个节点记录前一个节点然后遍历链表进行交换即可。时间复杂度O(n)空间复杂度O(1)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if (head null || head.next null) { return head; } ListNode node head, pre new ListNode(), result pre; while(node ! null node.next ! null) { pre.next node.next; pre node; ListNode temp node.next.next; node.next.next node; node.next temp; node node.next; } return result.next; } }方法二模拟 递归参考一每次调用该方法进行交换然后 a 指针指向下一个交换的头节点再调用该方法。时间复杂度O(n)空间复杂度O(n)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode swapPairs(ListNode head) { if (head null || head.next null) { return head; } ListNode result head.next; // 交换 ListNode temp head.next.next; head.next.next head; head.next swapPairs(temp); return result; } }