【LeetCode】24、两两交换链表中的节点

24、Swap Nodes in Pairs两两交换链表中的节点

难度：中等

题目描述

• 英文：

  Given a linked list, swap every two adjacent nodes and return its head.

  You may not modify the values in the list’s nodes, only nodes itself may be changed.

• 中文：

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

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

• 示例

  Example:

  Given 1->2->3->4, you should return the list as 2->1->4->3.

解题思路

思路一

进行Recursion探索时完成的，其他解法后续补充。

定义函数swap(head)，其中输入参数head表示链表的头结点。函数应该返回相邻节点交换后的新链表的头结点。

按如下步骤实现这个函数：

1. 首先，我们交换链表的前两个节点，即head和head.next；
2. 然后，我们递归调用函数swap(head.next.next)来处理链表的剩余部分；
3. 最后，获得步骤2返回的子链表的头结点，并将其和步骤1的新链表相连接；

代码提交

C++，用时4ms，内存9M

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *t = head->next;
        head->next = swapPairs(head->next->next);
        t->next = head;
        return t;
    }
};