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

链接：24.两两交换链表中的节点
难度：Medium
标签：递归、链表
简介：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

题解 1 - typescript

• 编辑时间：2020-10-13
• 执行用时：96ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：入队后两两交换顺序后重新组合。

function swapPairs(head: ListNode | null): ListNode | null {
  if (head === null) return null;
  const queue: ListNode[] = [];
  let temp: ListNode | null = head;
  while (temp !== null) {
    queue.push(temp);
    temp = temp.next;
    queue[queue.length - 1].next = null;
  }
  for (let i = 0, l = queue.length; i < l; i++) {
    if (i & 1) {
      let tempNode = queue[i];
      queue[i] = queue[i - 1];
      queue[i - 1] = tempNode;
    }
  }
  queue.forEach((v, i, arr) => {
    if (i !== 0) {
      arr[i - 1].next = v;
    }
  });
  return queue[0];
}

题解 2 - typescript

• 编辑时间：2020-10-13
• 执行用时：84ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：递归。

function swapPairs(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  const nextHead = head.next;
  head.next = swapPairs(nextHead.next);
  nextHead.next = head;
  return nextHead;
}

题解 3 - typescript

• 编辑时间：2020-10-13
• 执行用时：124ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：迭代。

function swapPairs(head: ListNode | null): ListNode | null {
  let tempNode = new ListNode(0, head);
  const headNode = tempNode;
  while (tempNode.next?.next) {
    const node1 = tempNode.next;
    const node2 = tempNode.next.next;
    tempNode.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    tempNode = node1;
  }
  return headNode.next;
}

题解 4 - typescript

• 编辑时间：2021-03-06
• 执行用时：88ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：进行每 2 个交换,25 题的特殊情况。

function _reverseList(head: ListNode, count: number): ListNode | null {
  if (count === 1 || head.next === null) return head;
  const tail = head.next;
  const nextList = _reverseList(tail, count - 1);
  head.next = tail.next;
  tail.next = head;
  return nextList;
}
function reverseList(head: ListNode, count: number): ListNode | null {
  let temp: ListNode | null = head;
  let c = count;
  while (--c && temp) temp = temp.next;
  return temp ? _reverseList(head, count) : head;
}
function swapPairs(head: ListNode | null): ListNode | null {
  const dummyHead = new ListNode(0, head);
  let temp: ListNode = dummyHead;
  while (temp !== null && temp.next !== null) {
    temp!.next = reverseList(temp.next!, 2);
    let count = 2;
    while (count-- && temp !== null) temp = temp.next!;
  }
  return dummyHead.next;
}

题解 5 - c

• 编辑时间：2021-11-19
• 内存消耗：5.8MB
• 编程语言：c
• 解法介绍：dfs。

struct ListNode* swapPairs(struct ListNode* head){
    if (!head) return NULL;
    if (head->next == NULL) return head;
    struct ListNode *next_node = head->next;
    if (next_node->next != NULL) head->next = swapPairs(next_node->next);
    else head->next = NULL;
    next_node->next = head;
    return next_node;
}

题解 6 - cpp

• 编辑时间：2023-08-06
• 执行用时：4ms
• 内存消耗：7.26MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    typedef pair<ListNode*, ListNode*> pll;
    ListNode* swapPairs(ListNode* head) {
        return swap(head, 1, 2).first;
    }
    pll swap(ListNode* node, int cnt, int max_cnt) {
        if (!node) {
            return make_pair(nullptr, nullptr);
        } else if (cnt == max_cnt) {
            node->next = swap(node->next, 1, max_cnt).first;
            return make_pair(node, node);
        } else if (!node->next) {
            return make_pair(node, node);
        } else {
            auto res = swap(node->next, cnt + 1, max_cnt);
            node->next = res.second->next;
            res.second->next = node;
            return res;
        }
    }
};

题解 7 - python

• 编辑时间：2023-08-06
• 执行用时：40ms
• 内存消耗：15.62MB
• 编程语言：python
• 解法介绍：同上。

def swap(node: Optional[ListNode], cnt: int, max_cnt: int) -> (Optional[ListNode], Optional[ListNode]):
    if not node:
        return (None, None)
    elif cnt == max_cnt:
        node.next = swap(node.next, 1, max_cnt)[0]
        return (node, node)
    elif not node.next:
        return (node, node)
    else:
        res = swap(node.next, cnt + 1, max_cnt)
        node.next = res[1].next
        res[1].next = node
        return res
    class Solution:
        def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
            return swap(head, 1, 2)[0]