算法题-两两交换链表中的节点【JS实现】_假设给定一个链表,请你设计一个程序实现两两交换

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

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

递归

/**
 * 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 next = head.next;
  head.next = swapPairs(next.next)
  next.next = head

  return next
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

非递归
两种不同的写法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
  // 记录当前节点的前驱节点
  let preNode = new ListNode(null);
  preNode.next = head;
  let prev = preNode;

  while (head !== null && head.next !== null) {
    let next = head.next;
    
    prev.next = next;    
    head.next = next.next
    next.next = head

    prev = head
    head = head.next
  }

  return preNode.next
}; 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

var swapPairs = function(head) {
  // 记录当前节点的前驱节点
  let preNode = new ListNode(null);
  preNode.next = head;
  let prev = preNode;

  while (prev.next !== null && prev.next.next !== null) {
    let node = prev.next, next = node.next;
    
    prev.next = next;    
    node.next = next.next
    next.next = node

    prev = node
  }

  return preNode.next
}; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18