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

作者:Choi Yang

更新于:6 个月前

字数统计:285 字

阅读时长:1 分钟

阅读量:

题目描述

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

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

示例:

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

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

解题思路

非递归解法

/**
 * 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 hummyHead = new ListNode(); // 虚拟节点
  hummyHead.next = head;
  let p = hummyHead;
  let node1, node2; // 当前要交换的两个节点
  while ((node1 = p.next) && (node2 = p.next.next)) {
    // 进行交换操作
    node1.next = node2.next;
    node2.next = node1;
    // 将链表串起来
    p.next = node2;
    p = node1;
  }
  return hummyHead.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 || !head.next) return head;
  let node1 = head,
    node2 = head.next;
  node1.next = swapPairs(node2.next);
  node2.next = node1;
  return node2;
};

学如逆水行舟，不进则退

Contributors

Choi Yang