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

题目描述

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

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

示例:

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

方法一（递归）：

将配对交换过程拆解为多个以两个元素为一对的子问题

…n(k-1) -> n(k)->n(k+1)->…

假如n(k+1)之后已经完成逆置，此时置换之后…->n(k-1)->n(k+1)->n(k)->…

Node *p = head -> next;

head -> next = p -> next;

p -> next = head;

实现如下:

ListNode* swapPairs(ListNode* head) {
    if(head == NULL || head -> next == NULL) {
        return head;
    }
    ListNode *p = head -> next;
    head -> next = swapPairs(p -> next);
    p -> next = head;
    
    return p;
}      

方法二（非递归）：

构造一个虚拟的头节点，同时当前链表遍历的结束条件：

如果链表长度为偶数，那么p->next->next = NULL

如果链表长度为奇数，那么p->next = NULL

p代表当前节点的上一个节点，next代表置换两个之后的下一个节点。

ListNode* swapPairs(ListNode* head) {
    ListNode * dummHead = new ListNode(0);
    dummHead->next = head;

    ListNode *p = dummHead;
    while(p->next && p->next->next){
        ListNode * node1 = p->next;
        ListNode * node2 = node1->next;
        ListNode * next = node2->next;

        node2->next = node1;
        node1->next = next;
        p->next = node2;
        
        p = node1;
    }
    return dummHead->next;      
}