LeetCode：两两交换链表中的节点

文章收录于LeetCode专栏 LeetCode地址

---

两两交换链表中的节点 题目

  给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。   示例 1：

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

  示例 2：

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

  示例 3：

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

算法思路

  该题需要我们把链表中的节点进行两两的交换，且必须要实际交换节点不能只是改变节点中的值。一次遍历完成两两交换，详细步骤如下，

定义一个独立的节点用来统领所有节点，同时定义一个用于遍历的临时节点对象；使用临时定义的节点temp开始遍历，且遍历条件是节点temp的下一个slow节点和下一个的下一个fast节点都不为空。因为slow节点和fast节点就是我们即将会在循环体中要进行交换的两个节点，所以这两个节点必须不能为空；在将slow节点和fast节点进行交换之前，需要将temp的下一个节点指向fast，这样做的目的就是连接前后的已经交换后的节点；交换slow节点和fast节点的位置，同时将用于遍历的temp节点指定为slow节点，用于下一轮遍历。

编码 /** * 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(Objects.isNull(head)){ return null; } ListNode newNode = new ListNode(-1); newNode.next = head; ListNode temp = newNode; while(temp.next != null && temp.next.next != null){ // 要被交换的节点一 ListNode first = temp.next; // 要被交换的节点二 ListNode second = temp.next.next; // 连接前后两个已经交换节点 temp.next = second; // 交换节点 first.next = second.next; second.next = first; // 指向下一个遍历节点 temp = first; } return newNode.next; } } 复杂度分析

  只有一次遍历所以空间复杂度为O(n)，空间复杂度为O(1)。

---

一键三连，让我的信心像气球一样膨胀！