[LeetCode 24] Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head.

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

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Diffculty
Easy

Similar Problems
[LeetCode ] Reverse Nodes in k-Group Hard

Analysis

// 思路1：最简洁的写法 // 每次按下一个pair的头结点来递归 class Solution { public: ListNode swapPairs(ListNode head) { if(head == nullptr || head->next == nullptr) return head; ListNode *newhead = head->next;

    ListNode *nextpair = head->next->next; // save the head of next pair
    head->next->next = head;
    head->next = swapPairs(nextpair);
    return newhead;
}

};

思路：

和reverse linked list很像，只不过每次reverse两个节点。同样要考虑奇偶数长度的情况。 并且由于头节点会变动，dummy节点又能派上用场了。 奇数： 1->2->3 2->1->3

偶数 1->2->3->4 2->1->4->3

要constant space所以不能用递归。那就用一个指针p边扫描边reverse。 用一个子函数来完成reverse pair并接回原链表的操作，返回值为pair的尾部，也就是p下一个移动位置。 D->1->2->3->4 | p

D->2->1->3->4 | r = swapNodes(p->next)

class Solution { public: ListNode swapPairs(ListNode head) { ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; while(head) head = swapNodes(head->next); head = dummy->next; delete dummy; return head; }

ListNode *swapNodes(ListNode *&head) {
    if(!head || !head->next) return NULL;
    ListNode *tail = head;
    ListNode *nextHead = head->next->next;
    head = head->next;
    head->next = tail;
    tail->next = nextHead;
    return tail;
}

};

不用子程序也可以用三指针扫描来完成： class Solution { public: ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy->next = head; ListNode prev = dummy, *cur = head;

    while(cur && cur->next) {
        prev->next = cur->next;
        cur->next = cur->next->next;
        prev->next->next = cur;
        prev = cur;
        cur = cur->next;
    }

    return dummy->next;
}

};