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

两两交换链表中的节点

方案一

需要建立dummy节点，注意在连接节点的时候

借助单链表实现

C-源代码

/**
 两两交换链表中的节点 1->2->3->4
 
 @param head 不带头结点
 @return 交换之后的链表 2->1->4->3
 */
struct ListNode *swapPairs(struct ListNode *head)
{
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *prev = dummy;
    prev->next = head;
    
    while (prev->next != NULL && prev->next->next != NULL) {
        
        struct ListNode *a = prev->next;
        struct ListNode *b = prev->next->next;
        
        struct ListNode *temp = b->next;
        prev->next = b;
        b->next = a;
        a->next = temp;
        prev = a;
    }
    
    return dummy->next;
}

/**
 两两交换链表中的节点测试
 */
void test_0024(void)
{
    int arr[4] = { 1, 2, 3, 4 };
    struct ListNode *head = linkListCreateHead(arr, sizeof(arr) / sizeof(arr[0]));

    printf("========两两交换链表中的节点测试========\n");
    
    printNode(head);
    struct ListNode *new = swapPairs(head->next);
    printNode(new);
}

方案二

利用了回溯的思想，递归遍历到链表末尾，然后先交换末尾两个，然后依次往前交换

借助单链表实现

C-源代码

struct ListNode *swapPairs2(struct ListNode *head)
{
    if (!head || !head->next) {
        
        return head;
    }
    
    struct ListNode *temp = head->next;
    head->next = swapPairs(head->next->next);
    temp->next = head;
    
    return temp;
}

参考Grandyang