Skip to content

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

作者:Choi Yang
更新于:6 个月前
字数统计:285 字
阅读时长:1 分钟
阅读量:

题目描述

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

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

示例:

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

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

解题思路

非递归解法

javascript
/**
 * 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;
};

递归解法

javascript
/**
 * 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;
};
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang