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

LeetCode 24. Swap Nodes in Pairs

LeetCode-24

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes.

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

method 1: 迭代

tmp->node1->node2 变成 tmp->node2->node1

ListNode* swapPairs(ListNode* head) {
    ListNode dummy = ListNode(0, head);
    ListNode *tmp = &dummy;
    while (tmp->next && tmp->next->next) {
        ListNode *node1 = tmp->next;
        ListNode *node2 = tmp->next->next;
        tmp->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        tmp = node1;
    }
    return dummy.next;
}

method 2: 递归

返回的是要交换的两两节点的下一个节点

ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *temp = head->next;    // 记录后向节点，待会会断开链接
    head->next = swapPairs(head->next->next);   // 先去处理下下个节点
    temp->next = head;      // 第二个节点指向第一个节点
    return temp;            // 返回新的头结点
}