​LeetCode刷题实战24：两两交换链表中的节点

今天和大家聊的问题叫做两两交换链表中的节点，我们先来看题面：

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed.

题意

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

样例

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解

递归法：

• 从链表的头节点 head 开始递归。
  
• 每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
  
• 下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。
  
• 交换了两个节点以后，返回 secondNode，因为它是交换后的新头。
  
• 在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点。
  

class Solution {
    public ListNode swapPairs(ListNode head) {
        // If the list has no node or has only one node left.
        if ((head == null) || (head.next == null)) {
            return head;
        }
        // Nodes to be swapped
        ListNode firstNode = head;
        ListNode secondNode = head.next;
        // Swapping
        firstNode.next = swapPairs(secondNode.next);
        secondNode.next = firstNode;
        // Now the head is the second node
        return secondNode;
    }
}

时间复杂度：O(N)，其中 NN 指的是链表的节点数量。空间复杂度：O(N)，递归过程使用的堆栈空间。好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。