如何成对反转链表

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

Node *reverse (Node *head, int k)  
{  
    Node* current = head;  
    Node* next = NULL;  
    Node* prev = NULL;  
    int count = 0;  
    while (current != NULL && count < k)  
    {  
        next = current->next;  
        current->next = prev;  
        prev = current;  
        current = next;  
        count++;  
    }  
    if (next != NULL)  
    head->next = reverse(next, k);  
    return prev;  
}

传递k的值为2

Answer 2

void pairWiseSwap(struct Node* head) 
{ 
    struct Node* temp = head; 

    /* Traverse further only if there are at-least two nodes left */
    while (temp != NULL && temp->next != NULL) { 
        /* Swap data of node with its next node's data */
        swap(&temp->data, &temp->next->data); 

        /* Move temp by 2 for the next pair */
        temp = temp->next->next; 
    } 
}

来源于GeeksForGeeks。

至于什么错误，已经指出prev已经是NULL了

 ListNode *current = head,*newHead = NULL,*temp = NULL,*prev = NULL;
 .
 .
 prev->next = temp;

我们不能使用 NULL->next，因为它会引发分段错误。

Answer 3

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;
}

如何成对反转链表

How to reverse a linked list in pairs

c

singly-linked-list