Swap nodes in a linked list in pairs

Topic describes

Given a linked list, swap adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, you need to actually swap nodes.

The sample

Example 1: input: head = [1,2,3,4] output: [2,1,4,3]

Example 2: Input: head = [] Output: []

Example 3: Input: head = [1] Output: [1]

Tip: The number of nodes in the list is in the range [0, 100] 0 <= node. val <= 100

Advanced: Can you solve this problem without changing the value of the linked list node? (That is, only the node itself is modified.)

Source: LeetCode link: leetcode-cn.com/problems/sw…

Analysis of the

List swapping, the first step is to find their precursor, and in this case the head node is also swapped, so create a new head node that points to the current first node. The following nodes are then swapped, defining the move pointer to be in the precursor of the two nodes to be swapped each time.

implementation

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; *}; * /

struct ListNode* swapPairs(struct ListNode* head)
{
    if(! head) {return NULL;
    }
    if (head->next == NULL) {
        return head;
    }
    
    // The first node is also swapped, so a header node is generated to return the result
    struct ListNode *h = (struct ListNode*)malloc(sizeof(struct ListNode));
    h->val = 0;
    h->next = head;

    struct ListNode *tmp = h;     // The last two nodes of the cursor TMP are swapped
    while(tmp->next ! =NULL&& tmp->next->next ! =NULL) {
        struct ListNode *p1 = tmp->next;
        struct ListNode *p2 = tmp->next->next;
        tmp->next = p2;
        p1->next = p2->next;
        p2->next = p1;
        tmp = p1;
    }
    return h->next;
}
Copy the code