0024._Swap_Nodes_In_Pairs.md

0024. Swap Nodes In Pairs

难度: Medium

刷题内容

原题连接

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

内容描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

  示例:

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

递归方式：思路主要是每次swapPairs返回的都是替换后的头指针，所以每次只替换两个，然后当前head.next指向的是移动两次指针后的swapParis返回结果

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = function(head) {
  if (!head || !head.next) {
    return head;
  }
  
  let root = head.next;
  head.next = swapPairs(head.next.next);
  root.next = head;
  return root;
};

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

这里借鉴了Python的解题思路

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const swapPairs = function(head) {
  if (!head || !head.next) {
    return head;
  }
  
  let tmp = new ListNode();
  tmp.next = head;
  
  let current = tmp;
  while (current.next && current.next.next) {
    let next1 = current.next;
    let next2 = current.next.next;
    let next3 = current.next.next.next;
    current.next = next2;
    next2.next = next1;
    next1.next = next3;
    current = next1;
  }
  
  return tmp.next;
};