c - 如何成对反转链表

Question

我想反转成对的链表，如果列表是 1->2->3->4->X那么它应该输出以下 2->1->4->3->X

我已经尝试解决这个问题，但它似乎没有运行。伙计们，你能帮我解决我的代码中的问题吗？

ListNode* reverseListInPairs(ListNode *head){
        ListNode *current = head,*newHead = NULL,*temp = NULL,*prev = NULL;
        while(current != NULL && current->next != NULL){

            temp = current->next;
            current->next = current->next->next;
            temp->next = current;
            prev->next = temp;
            prev = current;
            current = current->next;
            if(newHead == NULL){
                newHead = temp;
            }
        }
        return newHead;
    }

Answer 1

what is wrong in my code.

我看到的主要问题在这里:

            prev->next = temp;

在循环的第一次迭代中，prev 此时仍为 NULL，因此您正在执行空指针取消引用。

您可以解决该问题，并通过在真实节点前面引入合成头节点来删除列表头的特殊情况:

ListNode* reverseListInPairs(ListNode *head) {
    ListNode fake_head = { .next = head };
    ListNode *prev = &fake_head;
    ListNode *current = head;

    while (current != NULL && current->next != NULL) {
        ListNode *temp = current->next;

        current->next = current->next->next;
        temp->next = current;
        prev->next = temp;

        prev = current;
        current = current->next;
    }

    return fake_head.next;
}

我已经尽可能接近您的原始代码，但就我个人而言，我会进一步收紧它。特别是，您不需要在迭代中同时维护 current 和 prev；只需后者就足够了。

ListNode* reverseListInPairs(ListNode *head) {
    ListNode fake_head = { .next = head };
    ListNode *prev = &fake_head;

    while (prev->next && prev->next->next) {
        ListNode *first = prev->next;
        ListNode *second = first->next;

        prev->next = second;
        first->next = second->next;
        second->next = first;

        prev = first;
    }

    return fake_head.next;
}