24.两两交换链表中的节点

[chasingsnail]

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

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

 

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

递归

首先找到需要两两交换的两个节点 firstNode，secondNode（firstNode.next），将后者的 next 指向前者，而前者的 next 则指向递归调用函数后两个节点的交换结果。

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

  let firstNode = head
  let secondNode = head.next

  firstNode.next = swapPairs(secondNode.next)
  secondNode.next = firstNode

  return secondNode
}

迭代

迭代方法创建一个 prev 节点，在不断往后移动的过程中，不断地通过 prev 来修正分组中 firstNode 的指向。

ar swapPairs = function(head) {
  let dummy = new ListNode(-1)
  dummy.next = head
  
  let prevNode = dummy

  while (head !== null && head.next !== null) {
    let firstNode = head
    let secondNode = head.next

    // 节点交换
    prevNode.next = secondNode // 修正上一组 firstNode.next 指向
    firstNode.next = secondNode.next
    secondNode.next = firstNode
    
    head = firstNode.next
    prevNode = firstNode
  }
  
  return dummy.next
};